Linear Structures

Binary search

Halving the haystack every step

~11 minLesson 4 of 25Written by Claude Opus 4.8

Your first real algorithm - and the purest example of logarithmic thinking. Halve the problem every step, and a million items surrender in twenty questions.

You have played "guess my number between 1 and 100." You do not guess 1, 2, 3... you guess 50, then halve. That halving is binary search - and it is why you can find a name in a phone book of millions in a couple dozen glances. The catch: it only works on sorted data.

The idea in one line

Keep a range

[lo, hi]

that must contain the target. Look at the middle. It is either the target, too big (throw away the right half), or too small (throw away the left half). Each look halves what is left.

Step through it yourself

Click any value in the sorted array to search for it, then use Prev/Next to walk through the algorithm one comparison at a time. Watch the grayed-out cells: every step, half the remaining range disappears. The counters compare binary search against a plain left-to-right linear scan.

Binary-search stepper. Click a value to search for it, then step with Next.

Target is 42. It could be anywhere in the range lo...hi.

0binary-search looks

7linear-scan looks

Why "looks" grow so slowly

Each comparison throws away half the candidates. Starting from

n

items, how many halvings until one remains? Exactly

lo g_{2} n

. For

n = 1, 000, 000

that is about 20. A linear scan would need up to a million. This is why O(log n) feels like a cheat code.

Where the log comes from

After $k$ comparisons, the range has shrunk from $n$ to $n / 2^{k}$ . The search ends when only one candidate is left:

\frac{n}{2 ^{k}} = 1 ⟹ 2^{k} = n ⟹ k = lo g_{2} n .

So binary search runs in $O (lo g n)$ time - the number of steps is the number of times you can halve $n$ before hitting 1.

Writing it without bugs

Binary search is famous for being easy to get subtly wrong - the loop bounds and the $mid$ calculation are where off-by-one bugs live. Here is the clean version:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1          # inclusive range [lo, hi]
    while lo <= hi:                       # stop when the range is empty
        mid = lo + (hi - lo) // 2          # avoids overflow; same as (lo+hi)//2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1  # target is to the right
        else:                  hi = mid - 1  # target is to the left
    return -1                            # not found

Two classic traps

1. The sorted precondition. Binary search on unsorted data returns garbage - it is not "slow," it is wrong. 2. $mid = lo + (hi - lo) /2$ , not

(lo + hi) /2

: in languages with fixed-width integers,

lo + hi

can overflow. The subtraction form cannot.

Check yourself

What must be true of the array for binary search to be correct?

Roughly how many comparisons does binary search need for one million sorted items?

What does binary search throw away at each step, and what does that guarantee?

Recall the loop invariant. Try to state it, then check.

Lock it in

Keep a range $[lo, hi]$ that must contain the target, check the middle, and throw away the half that cannot hold it - each step halves what is left.
That halving runs in $O (lo g n)$ : the number of halvings from $n$ to 1 is $lo g_{2} n$ , about 20 for a million items.
It is only correct on sorted data; on unsorted input it is wrong, not merely slow.
Compute $mid = lo + (hi - lo) /2$ to avoid integer overflow, never $(lo + hi) /2$ .

Primary source

Chapter 1 of Grokking Algorithms introduces binary search with the friendliest diagrams around. To see it animate on your own input, use VisuAlgo or the USF search visualizer.

Ask your teacher

Curious about the "lower bound / upper bound" variants, or the powerful binary search on the answer pattern used in hard problems? Ask me. Later, this exact halving idea returns in the LLM path - top-p sampling binary-searches a probability cutoff.