-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search.py
More file actions
40 lines (34 loc) · 986 Bytes
/
Copy pathbinary_search.py
File metadata and controls
40 lines (34 loc) · 986 Bytes
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
def binary_search(s, a) -> int:
at_index = -1
if len(a) == 0:
return at_index
high = len(a) - 1
low = 0
while high != low:
middle = ((high - low) // 2) + low
if a[middle] == s:
at_index = middle
break
# if middle > s eliminate numbers greater than middle
elif a[middle] > s:
high = middle
# if middle < s eliminate numbers lower than middle
elif a[middle] < s:
low = middle + 1
return at_index
"""
def binary_search(s, a) -> int:
if len(a) == 0:
return -1
middle = len(a) // 2
if len(a) == 1 and a[middle] != s:
return -1
elif a[middle] == s:
return middle
# if middle > s eliminate numbers greater than middle
elif a[middle] > s:
binary_search(s, a[0: middle])
# if middle < s eliminate numbers lower than middle
elif a[middle] < s:
binary_search(s, a[middle + 1: len(a)])
"""