It’s possible to implement a binary search using recursion. Just like the loop version, we slice our sorted collection into halfs and check one half of the collection and discard the other half.
Here is the code
def binary_search(search_list, data, low, high): # This is the base case that # terminates the recursion if low <= high: # Find the mid point mid = int(low + (high - low) / 2) if search_list[mid] == data: # We found our item. Return the index return mid elif search_list[mid] < data: # Search the top half of search_list return binary_search(search_list, data, mid + 1, high) else: # Search the bottom half of the search_list return binary_search(search_list, data, low, mid - 1) 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', 0, len(names) - 1) if linda_index: print('Linda Belcher found at ', str(linda_index)) else: print('Linda Belcher was not found') teddy_index = binary_search(names, 'Teddy', 0, len(names) - 1) if teddy_index: print('Teddy was found at ', str(teddy_index)) else: print('Teddy was not found')
When run, we get the following output
Sorting names... Linda Belcher found at 2 Teddy was not found