Binary search

The idea

To find a value in an unsorted array you have to look at every element. In a sorted array, one comparison tells you much more: if the target is smaller than the value you looked at, it can only be to its left. Look at the middle value, and each comparison rules out half of what's left.

The algorithm

Keep two indices, lo and hi: the range that could still hold the target. They start at the two ends of the array. While lo ≤ hi:

1. mid = ⌊(lo + hi) / 2⌋, rounding down.
2. If the value at mid is the target, you're done.
3. If the target is smaller, go left: hi = mid − 1.
4. If it is larger, go right: lo = mid + 1.

If lo passes hi, the range is empty and the target isn't there. At that moment lo is the index where the target would have to be inserted to keep the array sorted, which is often just as useful.

in range could still be the target mid the value being compared out ruled out found the target

Where it goes wrong

Binary search is short, but it's famously easy to get subtly wrong:

• The ± 1. Setting lo = mid (instead of mid + 1) keeps a value you've already ruled out, and with two values left it can loop forever.
• Rounding. Pick one way to round mid and stick to it. These pages round down, as integer division does.
• Overflow. With fixed-size integers, lo + hi can overflow on huge arrays. Writing mid = lo + ⌊(hi − lo) / 2⌋ gives the same index safely.

Cost

	Binary search	Linear search
Comparisons	At most ⌊log₂ n⌋ + 1: 4 for the 11 values above, 20 for a million	Up to n
Needs	Sorted data with fast access by index	Nothing

A binary search tree stores the same idea as a structure: each node is a "mid", and each comparison picks a side.

Start the walkthrough →