Binary search: how to find one number in a million with 20 guesses

Imagine a friend thinks of a number from 1 to 1,000,000 and says only "higher" or "lower" after each guess. Guessing 1, then 2, then 3 could take a million tries. Guessing smartly takes at most 20. The smart way is called binary search, and it is one of the most useful ideas in programming.

The idea: throw away half every time

Start by guessing the number in the middle. If your friend says "higher", you now know the answer is in the top half, so the whole bottom half is gone. Guess the middle of what is left, and repeat. Each guess cuts the remaining possibilities in half.

There is one requirement: the items must already be sorted (smallest to largest, or A to Z). Without order, "higher" and "lower" would tell you nothing about where to look next.

Try it: 64 sorted numbers

Tap any number to make it the target (it gets a dashed orange outline). Then press Step to make one guess. The bright cell is the guess, bright-bordered cells are still possible, and faded cells have been ruled out.

Try the first number, then the last, then one in the middle. Notice that a target near the left edge costs a plain scan almost nothing, but binary search never needs more than 7 guesses here, whichever number you pick.

The same thing in Python

Keep two markers, low and high, around the part of the list that could still hold the answer. Each loop looks at the middle one:

def binary_search(items, target):
    low, high = 0, len(items) - 1
    guesses = 0
    while low <= high:
        mid = (low + high) // 2      # // rounds down to a whole number
        guesses += 1
        if items[mid] == target:
            return mid, guesses      # found it: position and guess count
        elif items[mid] < target:
            low = mid + 1            # target is in the upper half
        else:
            high = mid - 1           # target is in the lower half
    return -1, guesses               # -1 means "not in the list"

Running it on a sorted list of every number from 1 to 1,000,000 gives these real results:

numbers = list(range(1, 1_000_001))
print(binary_search(numbers, 737_421))    # (737420, 20)
print(binary_search(numbers, 1))          # (0, 19)
print(binary_search(numbers, 2_000_000))  # (-1, 20)

The first number is the position (counting from 0) and the second is how many guesses it took. Finding 737,421 in a million numbers took 20 guesses. A number that is not in the list at all took 20 guesses to rule out, instead of a million.

Why 20?

Ask the question backwards: how many times can you halve a million before you reach 1? Halving 1,000,000 repeatedly goes 500,000, 250,000, 125,000 and so on, and it takes about 20 halvings. Each extra guess doubles the size of list you can handle:

Items in the list	Most guesses needed
64	7
1,000	10
1,000,000	20
1,000,000,000	30

A billion items need only 30 guesses. Programmers write this growth as O(log n), read as "logarithmic": the work grows very slowly as the data grows. A plain scan from the left is O(n): a thousand times more data means a thousand times more work.

Where beginners trip up

The list must be sorted. Run the function on the unsorted list [5, 1, 9, 3] and searching for 5 returns -1 ("not found") even though 5 is the first item, with no error message.

Sorting costs something too. If you only search a list once, a plain scan is fine. Binary search pays off when you search the same sorted data many times, which is what a phone's contact list or a database index does.

Off-by-one mistakes. Writing low = mid instead of low = mid + 1 can make the loop repeat forever, because the middle guess is already known to be wrong and must be excluded.

Use the built-in version

In real code you rarely write this by hand. Python's standard library has a bisect module that does the halving for you:

from bisect import bisect_left
print(bisect_left([2, 4, 6, 8, 10], 6))   # 2

It returns the position where the value is, or where it would be inserted to keep the list sorted. Check that the item at that position equals your target before treating it as found. The idea underneath is the same one you just stepped through: halve, compare, repeat.