PythonProblemSolving/BinarySearch.py at master · ebaumstarck/PythonProblemSolving · GitHub

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
defbinary_search(sortedList, num=None, start=None, end=None):
'''
 binary search recursively
 '''
ifnumisNone:
raiseError("I can't search for nothing!")
ifstartisNone:
start=0
ifendisNone:
end=len(sortedList) -1

ifstart>end:
returnFalse
middleIdx= (start+end) /2
middle=sortedList[middleIdx]
ifnum<middle:
returnbinary_search(sortedList,num,start,middleIdx-1)
elifnum>middle:
returnbbinary_search(sortedList,num,middleIdx+1, end)
else:
returnTrue

defbinary_search_iter(sortedList,num=None, start=None, end=None):
'''
 binary search iteratively
 '''
ifstartisNone:
start=0
ifendisNone:
end=len(sortedList) -1
whilestart<=end:
printstart, end
middleIdx= (start+end) /2
middle=sortedList[middleIdx]
ifnum>middle:
start=middleIdx+1
elifnum<middle:
end=middleIdx-1
else:
returnTrue
returnFalse