Binary Search Algorithm (Recursive)

binary_search.py

def binary_search(ordered_list, search_item):

    # If the length of the list is zero, it's empty,
    # so the search_item can't be in the list.
    if len(ordered_list) == 0:
        return False

    # Otherwise, let's try to find the item...
    else:
        middle_item = len(ordered_list) // 2

        if search_item == ordered_list[middle_item]:
            return True

        elif search_item < ordered_list[middle_item]:
            # The item we're looking for is smaller than the item in the middle.
            #
            # For example:
            # We're looking for a 5, but the item in middle of the list is 7.
            # We should throw out the second half of the list because we know
            # everything in that half is larger than 7.
            #
            # Continue searching the first half of the list,
            # which is everything from the beginning up to the middle item.
            return binary_search(ordered_list[:middle_item], search_item)

        elif search_item > ordered_list[middle_item]:
            # The item we're looking for is larger than the item in the middle.
            #
            # For example:
            # We're looking for a 7, but the item in the middle of the list is 5.
            # We should throw out the first half of the list because we know
            # everything in that half is smaller than 5.
            #
            # Continue searching the second half of the list.
            # Start at middle_item + 1 because we already looked at middle_item.
            return binary_search(ordered_list[middle_item + 1:], search_item)