Binary search visualizer

Pick a search and a target, then press Step or Play. Each step compares the target with the middle of the cells that are still possible and greys out the half that cannot hold the answer. The log on the right lists every comparison. New sorted array draws another array, with some values repeated.

• Pick a target that appears more than once and run all three searches. Find stops at whichever copy it happens to hit first; lower bound always ends on the first copy and upper bound just after the last.
• Pick a target that is not in the array. Find reports that it is missing; lower and upper bound both point to where it would be inserted to keep the array sorted.
• Try a target larger than every value. The bounds return the position past the end, shown as an extra cell.

The searches are tested against a plain left-to-right scan on thousands of random arrays, for every target, and never take more than the worst-case number of comparisons.

Binary search is an algorithm for finding a value in a sorted list. It compares the target with the middle element; if the middle is smaller, the target can only be in the upper half, and if it is larger, only in the lower half. Each comparison discards half of what is left, so a list of a million items takes at most 20 comparisons and a billion at most 30.

It is the method people use with a dictionary or a phone book, opening near where the word should be and narrowing down, made exact. It needs random access to the middle of the list, which is why it works on arrays but not on linked lists, and it needs the list to be sorted, which is why databases and file systems keep their indexes in sorted structures such as B-trees.

The search keeps two indexes, lo and hi, marking the part of the array where the target could still be. The classic version keeps this invariant: if the target is in the array at all, it is somewhere between lo and hi.

1. Start with lo = 0 and hi = n − 1, the whole array.
2. While lo ≤ hi, take the middle index mid = lo + (hi − lo) / 2, rounded down.
3. If the value at mid is the target, return mid. If it is smaller, set lo = mid + 1; if larger, set hi = mid − 1.
4. If lo passes hi, the window is empty and the target is not present; lo is where it would go.

Every step either finds the target or removes mid and everything on one side of it, so the loop always ends. Most bugs in binary search come from breaking the invariant at the edges: setting hi = mid instead of mid − 1 in a closed interval, or looping on lo < hi when the interval is closed.

The classic search answers "is it here?" and returns whichever copy it happens to find. Often the question is different: where does the first copy start, or where would a new value go? Lower bound returns the first position whose value is at least the target, and upper bound the first position whose value is greater than it. Both use a half-open window from lo up to, but not including, hi, starting with hi = n so that "past the end" is a possible answer.

Instead of stopping at a match, they keep going until the window is a single position. When the middle value could be the answer, mid stays in the window (hi = mid); otherwise it is dropped (lo = mid + 1). The two differ only in whether equal values count as "too small". Together they answer several common questions:

• Number of copies of x: upper bound − lower bound.
• Where to insert x to keep the array sorted: lower bound (before equal values) or upper bound (after them, which keeps insertion order stable).
• All values between x and y: from lower bound of x up to upper bound of y.
• The nearest value to x: one of the two items next to its lower bound.

After k comparisons at most n / 2^k items remain, so the search needs at most ⌊log₂ n⌋ + 1 comparisons. Growing the array a thousandfold adds only about ten:

Binary search is short but easy to get wrong. The usual mistakes are mixing closed and half-open intervals, which either skips the last candidate or loops forever when the window has two items, and returning the wrong index when the target is missing.

A subtler bug lasted for decades. Computing the middle as (lo + hi) / 2 overflows when the indexes are large: with 32-bit signed integers, lo = 1,200,000,000 and hi = 1,300,000,000 add up to more than 2,147,483,647, the sum wraps around, and (lo + hi) / 2 gives -897,483,648 instead of 1,250,000,000. In 2006 Joshua Bloch reported that this line had been in Java's Arrays.binarySearch for about nine years, and that the binary search Jon Bentley proved correct in Programming Pearls had the same flaw; it only shows up on arrays of around a billion elements. The fix is to compute lo + (hi − lo) / 2, or in Java (lo + hi) >>> 1. The simulator uses the first form.

Binary search does not need an array, only a yes/no question whose answer flips once: no, no, no, then yes from some point on. Lower bound is exactly "find the first yes". That pattern solves problems such as:

• The smallest truck capacity that can ship all packages within a number of days: capacity x either works or not, and if x works, so does anything larger.
• The integer square root of n: the largest x with x² ≤ n.
• The first bad commit in a history, which is what git bisect does, asking you to test the middle commit each time.

The search runs over the range of possible answers instead of array indexes, and needs about log₂ of the range's size checks.

According to Donald Knuth, binary search was first mentioned in print by John Mauchly in 1946, in the Moore School Lectures on electronic computers. Early versions only worked for array sizes one less than a power of two; Knuth credits D. H. Lehmer with the first version that worked for every n, in 1960. Despite being one of the first algorithms students learn, it has stayed a byword for subtle bugs, from off-by-one errors to the overflow Bloch described in 2006.