Binary search

Cost and properties

time	O(log n)
compares	≤ 1 + lg n
requires	a sorted array
space	O(1)

Reference: Sedgewick & Wayne, §1.1, §3.1.

Binary search in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def binary_search(a, key):
    # PRECONDITION: a is sorted.
    # INVARIANT: if key is in a, it is inside a[lo..hi].
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2         # no overflow, unlike (lo+hi)//2
        if key < a[mid]:
            hi = mid - 1                  # discard mid and everything right
        elif key > a[mid]:
            lo = mid + 1                  # discard mid and everything left
        else:
            return mid
    return -1                             # lo > hi: the interval is empty

Why it works

The invariant is the algorithm

Everything follows from one sentence: if the key is present at all, it lies in a[lo..hi]. Each comparison against a[mid] lets you throw away half of that interval while keeping the sentence true. The loop ends when the interval is empty (lo > hi), which is a proof the key is absent — not a guess.

Why lg n

The interval size goes n, n/2, n/4, … and the search stops when it hits 1. The number of halvings is lg n: 20 compares for a million keys, 30 for a billion. Try the 31-key preset — exactly 5 compares, because 2⁵ = 32.

Two bugs that are famous for a reason

• (lo + hi) // 2 overflows in fixed-width languages. Java's own binary search carried this bug for nine years. Writing lo + (hi - lo) // 2 costs nothing and cannot overflow.
• hi = mid instead of mid - 1 gives an infinite loop when lo == hi. The interval must strictly shrink every iteration.

Where the course uses it

The whitelist filter, and then everywhere: 3-sum drops from n³ to n² lg n by sorting and binary-searching for -(a[i] + a[j]). That is the reduction pattern the whole course leans on — sorting is not the goal, it is the enabler.

What to try in the animation

The array is sorted for you if you enter it out of order — binary search on unsorted input is the classic silent bug.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• hit — keys: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 · key: 33
• miss — keys: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 · key: 50
• first element — keys: 6 13 14 25 33 43 51 53 64 72 84 93 95 96 97 · key: 6
• 31 keys (5 compares) — keys: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 · key: 27

Open Binary search in the player →

The rest of Analysis of algorithms

• 3-sum (brute force) Count triples summing to zero by trying all of them.