Recursive Binary Search—Python

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