Binary search

To find out whether a value is in a list, in (or a loop) looks at the items one by one from the start. That's a linear search. In a list of a million items, it may have to look at all million.

If the list is sorted, there's a much faster way. Think of guessing a number between 1 and 100 when you're told "higher" or "lower" after each guess. You start with 50, and whatever the answer, half of the numbers are out of the game. Binary search does the same with a sorted list:

1. Look at the item in the middle of the search area.
2. If it's the one you're looking for, you're done.
3. If it's smaller than what you're looking for, the target can only be in the right half. Search there.
4. If it's greater, search the left half.
5. If the search area is empty, the value isn't in the list.

Steps 3 and 4 are the same search on a smaller area, so recursion fits well. The function gets the list, the target and the edges of the search area, low and high, as indexes. It returns the target's index, or -1 when the target isn't there. A print in each call shows how the area shrinks:

def find(numbers, target, low, high):
    if low > high:
        return -1
    middle = (low + high) // 2
    print(f"searching {low}..{high}, middle item {numbers[middle]}")
    if numbers[middle] == target:
        return middle
    if numbers[middle] < target:
        return find(numbers, target, middle + 1, high)
    return find(numbers, target, low, middle - 1)


numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(find(numbers, 23, 0, len(numbers) - 1))
print(find(numbers, 10, 0, len(numbers) - 1))

searching 0..9, middle item 16
searching 5..9, middle item 56
searching 5..6, middle item 23
5
searching 0..9, middle item 16
searching 0..3, middle item 5
searching 2..3, middle item 8
searching 3..3, middle item 12
-1

The first call searches the whole list, from index 0 to len(numbers) - 1. (low + high) // 2 is the index in the middle, rounded down. When the middle item is too small, the new area starts at middle + 1: the middle item has been checked already, so it's left out. In the second search, the last call gets low 3 and high 2. The area is empty, and that's the base case that returns -1.

Why it's fast

Every call halves the search area. A list of 10 items needs at most 4 looks, and a list of a million items needs at most 20, because a million can be halved only about 20 times before a single item is left. A linear search might need a million looks.

A wrapper, and a warning

So that the people who use the search don't need to think about low and high, you can wrap it in a function of its own. Here contains starts the search on the whole list and turns the index into True or False. Binary search works on anything sorted, such as words in alphabetical order, since < compares strings alphabetically:

def find(numbers, target, low, high):
    if low > high:
        return -1
    middle = (low + high) // 2
    if numbers[middle] == target:
        return middle
    if numbers[middle] < target:
        return find(numbers, target, middle + 1, high)
    return find(numbers, target, low, middle - 1)


def contains(items, target):
    return find(items, target, 0, len(items) - 1) != -1


print(contains([2, 5, 8, 12, 16], 12))
print(contains(["ant", "bee", "cat", "dog"], "cat"))
print(contains([9, 2, 7, 4, 1], 9))

True
True
False

The last answer is wrong: 9 is in the list. But the list isn't sorted, and binary search trusts the order. It looked at 7 first, decided that 9 could only be on the right, and never saw the 9 at the start. Binary search only works on a sorted list.