Binary search, deeply

Binary search, deeply

If the list is sorted, something drastic becomes possible: check the middle element and throw away half the list.

• Middle value too small? The target can only be in the right half.
• Middle value too big? It can only be in the left half.
• Equal? Done.

Each check halves what remains, so 1,000,000 becomes 500,000, then 250,000, and so on down to 1. That takes about log₂(n) checks, so a million items need about 20 rather than a million.

The sorted requirement is what makes the discarding valid. In an unsorted list, a middle value smaller than the target says nothing at all about which side the target is on.

This is binary search, the single most-tested algorithm in interviews, and also the one with the most famous off-by-one bugs. It is worth writing slowly and correctly rather than from memory.

Watching the range shrink

The print inside the loop traces which index gets checked and how the range narrows.

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        print(f"checking index {mid} (value {nums[mid]}), range [{lo}, {hi}]")
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("found at", binary_search(nums, 23))

Output

checking index 4 (value 16), range [0, 9]
checking index 7 (value 56), range [5, 9]
checking index 5 (value 23), range [5, 6]
found at 5

Three checks located an item among ten, and the trace shows what each one bought.

The first check at index 4 found 16, which is smaller than 23, so lo jumped to 5 and indexes 0 through 4 left the search for good. The second check found 56, too big, so hi dropped to 6.

By the third turn the range was [5, 6], just two candidates, and the middle of those is index 5, which holds the answer.

Note the arithmetic on the range bounds. lo = mid + 1 and hi = mid - 1 both step past the checked index, since that index has already been ruled out and leaving it in would risk checking it forever.

A full trace, by hand

Interviewers routinely ask for a paper trace of binary search, because the trace exposes whether you actually know where lo, hi, and mid go.

Searching for 23 in [4, 8, 15, 16, 23, 42, 77, 91], at indexes 0 through 7.

Three checks for eight items, which is log₂(8) = 3 exactly.

Step 3 is the one to look at hard. lo and hi are equal, and the loop still runs, which is precisely why the condition has to be lo <= hi rather than lo < hi. A range of one element still contains one unchecked element.

When the target is missing, the same shrinking continues until hi slips below lo, and the loop exits empty-handed. Every step either finds the answer or strictly shrinks the range, so the loop cannot run forever.

It stops when lo and hi cross, so hi is smaller than lo and the lo <= hi condition fails.

Every miss moves lo above mid or hi below mid, so the range strictly shrinks on every turn. That is what guarantees termination, since a range that only ever gets smaller must eventually be empty.

When hi finally slips below lo, the range holds nothing. At that moment the invariant becomes the proof: the target, if it exists, is inside [lo, hi], and [lo, hi] is empty, so the target does not exist.

The function then returns −1. That is a genuine conclusion about the whole list rather than a giving-up, which is the difference from a linear scan that has to touch everything to say the same thing.

The three classic bugs

Almost every broken binary search fails in one of three places, so this checklist is worth memorizing.

1. The loop condition is lo <= hi, not lo < hi. When lo == hi there is still one unchecked element, and the strict version silently misses answers sitting there.
2. Move past mid with lo = mid + 1 and hi = mid - 1. Writing lo = mid can loop forever, because a two-element range keeps computing the same mid and never shrinks.
3. The list must be sorted. Binary search on unsorted data returns garbage without crashing, which is worse than crashing, since nothing signals that the answer is wrong.

That third one is the failure most likely to reach production. The first two break loudly in testing, while an unsorted input just quietly returns −1 for values that are present.

One more habit: say the invariant out loud. The target, if it exists, is always inside [lo, hi]. Every line of the function exists to keep that sentence true, and any line that breaks it is the bug.

About 20 checks.

Each check halves the range, so the question is how many halvings take a million candidates down to one, which is log₂(1,000,000) ≈ 20.

The more striking fact is what happens next. Doubling the list to two million adds exactly one more check, because one extra halving is all a doubled input requires.

That is what O(log n) feels like in practice, and it is why binary search scales to data sizes where a linear scan is hopeless. A billion items need about 30 checks.

Compare the linear search from lesson 2-1, which needed 5,000 comparisons for 5,000 items. Sorting the data once converts that cost from n into log₂ n for every search afterwards.

Counting the checks on a million items

The same search with a counter, run against the log₂ prediction.

def binary_search_count(nums, target):
    lo, hi = 0, len(nums) - 1
    checks = 0
    while lo <= hi:
        checks += 1
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid, checks
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, checks

nums = list(range(1_000_000))
print(binary_search_count(nums, 999_999))
print(binary_search_count(nums, -5))

Output

(999999, 20)
(-1, 19)

The only change from the traced version is checks += 1 as the first line inside the loop, which counts one check per turn.

Twenty checks for a million items is the prediction coming true, since log₂(1,000,000) ≈ 19.9. Nothing about the data was favorable, and the target was the very last element.

The miss cost 19, slightly fewer than the hit. A miss ends as soon as the range empties, while this particular hit needed one final comparison to confirm the value.

The comparison with lesson 2-1 is the point of the exercise. The same list searched linearly costs up to 1,000,000 comparisons, so sorted order plus 20 checks is a fifty-thousandfold improvement.