Binary Search—Python

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