start with a sorted list of data
see if the mid value is what we're looking for
if item is lower than the mid, make mid-1 the new high point
if item is higher than the mid, make mid+1 the new low point
keep going until list is exhausted or item is found

The data doesn't really matter, so using a simple range of numbers:



In [2]:

    
data = [i for i in range(10000)]
data[:10]









    Out[2]:





[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

straight forward binary search

implementing this using a while loop



In [3]:

    
def binary_search(data, item):
    """takes in a sorted list of items, and item to find, and returns item number if item found, -1 if not found"""
    
    low = 0
    high = len(data) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == item:
            return mid
        elif data[mid] < item:
            low = mid + 1
        else:
            high = mid - 1
    return -1

binary_search(data, 10)









    Out[3]:





10

Recursive attempt at binary search

Note: this only prints out yes if item found, msg otherwise



In [20]:

    
def binary_search_recursive(data, item):
    """
    takes in a sorted list and item to find
    returns index number if found, -1 if not"""
    
    def recur(low, high):
        mid = (low + high) // 2   
        if low > high:
            return -1
        elif item < data[mid]:
            return recur(low, mid-1)
        elif item > data[mid]:
            return recur(mid+1, high)
        else:
            #print('found', item, 'in position', mid)
            return mid
        
    return recur(0, len(data) - 1)



In [21]:

    
binary_search_recursive(data, 2)









    Out[21]:





2

Comparing the two



In [ ]:

    
# non-recursive
%timeit(binary_search(data, 2))









    



4.15 µs ± 175 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)



In [ ]:

    
# recursive
%timeit(binary_search_recursive(data, 2))

So a straightforward algo is faster.

testing got it correct:



In [ ]:

    
for i in range(0,100):
    assert i == binary_search(data, i)
    assert i == binary_search_recursive(data,i)



In [ ]:

    
binary_search(data,-1)



In [ ]:

    
binary_search_recursive(data,-1)



In [ ]: