-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.py
58 lines (50 loc) · 1.65 KB
/
search.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
"""
Search algorithms
"""
def linear_search(array: list[int], target: int) -> int | None:
"""
The simplest search algorithm. O(n)
:param array: Array to search in
:param target: Target element to find
:return: index of found element or None
"""
for i, element in enumerate(array):
if element == target:
return i
return None
def binary_search(array: list[int], target: int) -> int | None:
"""
Divide and check again. O(log(n))
:param array: Array to search in
:param target: Target element to find
:return: index of found element or None
"""
start, end = 0, len(array) - 1
while start <= end:
check_index = (start + end) // 2
check_value = array[check_index]
if check_value == target:
return check_index
if check_value < target:
start = check_index + 1
else:
end = check_index - 1
return None
def binary_search_recursive(array: list[int], target: int) -> int | None:
"""
Divide and check again, but recursively O(log(n))
:param array: Array to search in
:param target: Target element to find
:return: index of found element or None
"""
def search(_array, _target, _start, _end):
check_index = (_start + _end) // 2
check_value = array[check_index]
if _start > _end:
return None
if check_value == target:
return check_index
if check_value < target:
return search(_array, _target, check_index + 1, _end)
return search(_array, _target, _start, check_index - 1)
return search(array, target, 0, len(array) - 1)