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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s