Recursive Binary Search

Recursive Binary Search Example¶

In [1]:

def binSearchR(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
            return True
        else:
            if item<alist[midpoint]:
                return binSearchR(alist[:midpoint],item)
            else:
                return binSearchR(alist[midpoint+1:],item)

In [2]:

sortedList = [0,2,4,8,16,18,19]
for x in range(21):
    print(x,binSearchR(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