Binary search step by step

TL;DR:

• Binary search finds a target in a sorted list by checking the middle and discarding the half that cannot contain it.

• Each guess halves the possibilities, so 100 numbers need at most 7 guesses, because 2⁶ = 64 is too few and 2⁷ = 128 is enough.

• It only works if the data is sorted.

A friend picks a number from 1 to 100 and says 'higher' or 'lower' after each guess. Guessing 1, 2, 3 can take 100 tries. Guessing smartly always takes 7 or fewer. The smart method is binary search, and the game is the clearest way to learn it.

The idea in plain words

Binary search finds a target in a sorted list. Look at the middle item. If it is the target, you are done. If the target is smaller, it can only be in the left half, so throw the right half away. If it is larger, throw the left half away. Repeat on what remains until you find the target or run out of items.

The word 'sorted' matters. The method works because the order tells you which half to discard. On an unsorted list the middle item tells you nothing about where the target is.

Why halving is so powerful

Each guess removes half the possibilities. Starting from 100 numbers, the count of candidates after each guess is at most 50, 25, 12, 6, 3 and 1, and the seventh guess finishes the job. That is because 2⁶ = 64 is less than 100, so 6 guesses cannot always be enough, while 2⁷ = 128 is at least 100, so 7 always are. In general you need about log₂ n guesses for n items.

Worked example: the secret number is 73

Say the secret number is 73. Track the range that is still possible, and always guess the middle, rounding down.

The candidates fell from 100 to 50, 24, 12, 6, 3, then to 1. Six guesses found it, within the limit of 7. The worst case is a number like 100 or 1 at the end of a run, which could use all 7.

Now in code. The list below is the numbers 1 to 100, so items[i] equals i + 1.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = list(range(1, 101))
print(binary_search(numbers, 73))

Trace it. At the start low = 0, high = 99. Then mid = 49 holds 50, which is less than 73, so low = 50. Next mid = 74 holds 75, too big, so high = 73. Then mid = 61 holds 62, so low = 62; mid = 67 holds 68, so low = 68; mid = 70 holds 71, so low = 71; and mid = 72 holds 73. It returns index 72, so the program prints 72. Index 72 is the 73rd number, as expected. That is six passes, matching the table.

What happens when the target is missing

Search the sorted list [2, 4, 6, 8, 10, 12, 14] for 9, which is not there. Start with low = 0, high = 6.

1. mid = 3 holds 8, which is less than 9, so low = 4.

2. mid = (4 + 6) // 2 = 5 holds 12, which is greater than 9, so high = 4.

3. mid = (4 + 4) // 2 = 4 holds 10, greater than 9, so high = 3.

4. Now low = 4 is greater than high = 3, so the loop stops and the function returns -1.

Three looks were enough to prove that 9 is absent, among seven items. A scan would have needed to check every item. The same halving works for any sorted data, such as words in a dictionary or timestamps in a log.

Why the loop condition is `low <= high`

When low equals high, exactly one candidate remains, and it still has to be checked. That is why the condition uses <=. Only when low has moved past high is the candidate range truly empty. This single character is behind many wrong versions of binary search, so it is worth tracing a one-item list by hand: with [5] and target 5, low = high = 0, mid = 0, and the function returns 0 on the first pass.

The + 1 and − 1 matter for a similar reason. After checking mid, you know it is not the target, so it must leave the range. If you keep it, the range might never shrink.

How to check your answer

• The range should shrink on every pass. If it does not, you have an infinite loop.

• The target, if it exists, must always be between low and high.

• Count passes and compare with the bound: no more than ⌊log₂ n⌋ + 1, here 6 + 1 = 7.

• Test the edges: the first item, the last item, a missing item, and a one-item list.

Common mistakes

• Using it on unsorted data.

• Writing low = mid or high = mid instead of mid + 1 and mid − 1, which can loop forever.

• Using < instead of <= in the while condition, which misses the last remaining item.

• Forgetting that the function returns an index, not the value. Here the index is 72 and the value is 73.

Where you will use it next

The halving idea is behind fast lookups in databases and in debugging by narrowing a range. To see how it compares with other growth rates, read Big O notation with everyday examples, and for the algorithms that put data in order first, see sorting algorithms compared.

Frequently asked questions

What if the target is not in the list?

The range empties and low passes high. The loop ends and the function returns -1.

Does binary search work on a linked list?

Not well. It needs fast access to the middle item, which arrays and Python lists provide.