Binary searches work by splitting a collection in half and only searching on half of the collection while discarding the other half. This algorithm requires the collection to be sorted first.
Here’s the code
def binary_search(search_list, data): low = 0 high = len(search_list) - 1 while low <= high: mid = int(low + (high - low) / 2) if search_list[mid] == data: # Return the index because we # found our item return mid elif search_list[mid] < data: # Continue search at the top # half of search list low = mid + 1 else: # Continue search at the # bottom of search list high = mid - 1 # The item wasn't found return None if __name__ == '__main__': names = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] print('Sorting names...') names.sort() linda_index = binary_search(names, 'Linda Belcher') if linda_index: print('Linda Belcher found at ', str(linda_index)) else: print('Linda Belcher was not found') teddy_index = binary_search(names, 'Teddy') if teddy_index: print('Teddy was found at ', str(teddy_index)) else: print('Teddy was not found')
When run, we will get the following output.
Sorting names... Linda Belcher found at 2 Teddy was not found