The data doesn't really matter, so using a simple range of numbers:
data = [i for i in range(10000)]
data[:10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
implementing this using a while loop
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)
10
Note: this only prints out yes if item found, msg otherwise
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)
binary_search_recursive(data, 2)
2
# non-recursive
%timeit(binary_search(data, 2))
4.15 µs ± 175 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# recursive
%timeit(binary_search_recursive(data, 2))
So a straightforward algo is faster.
for i in range(0,100):
assert i == binary_search(data, i)
assert i == binary_search_recursive(data,i)
binary_search(data,-1)
binary_search_recursive(data,-1)