-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_search.py
31 lines (27 loc) · 1019 Bytes
/
binary_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
def binary_search(L,x):
"""Binary search algorithm to find target x in list L
cost: O(log_2(N)) since if we double the number of elem in the list, the number of iterations needed only increases by one
(as halfing the list is one iter).
"""
#Set initial start and end indices for full list
istart = 0
iend = len(L)-1
#Contract "active" portion of list
while istart<=iend:
imid = int(0.5*(istart+iend))
if x==L[imid]:
return imid
elif x < L[imid]:
#cut off right half of list
iend = imid-1
else:
#cut off left half of list
istart = imid+1
#we keep spliting and cutting untill we land on element we are looking for.
#we keep track of element index through imid
return -1
if __name__ == "__main__":
L = [1,4, 6, 13, 35, 66, 79, 89, 90]
#set target
x = 89
print(f"index of element {x} is {binary_search(L, x)}")