Binary Search

Bare Bones Binary Search Example¶

In [1]:

def binSearch(Alist, v):
    low = 0                   
    high = len(Alist)-1

    while low<=high:
        mid = (low+high)//2   # floor division
        if Alist[mid] < v:
            low=mid+1
        elif Alist[mid] > v:
            high = mid-1
        else:
            return True

    return False

In [2]:

sortedList = [0,2,4,8,16,18,19]
for x in range(21):
    print(x,binSearch(sortedList,x))

0 True
1 False
2 True
3 False
4 True
5 False
6 False
7 False
8 True
9 False
10 False
11 False
12 False
13 False
14 False
15 False
16 True
17 False
18 True
19 True
20 False