A lesson from the data structures and algorithms bootcamp. About a 12 minute read.
Halve the search range, repeat, and a million items take about twenty steps. Everybody can describe binary search and a famous study found that most published implementations of it were wrong, including one that shipped in a standard library for nine years. The idea is trivial. The boundaries are not, and the way to stop getting them wrong is to stop thinking about the target and start thinking about an invariant.
Look at the middle. If it is too small, the answer is in the right half; if too big, the left half. Throw away the half that cannot contain it and repeat. Each step halves the range, so the count of steps is log2(n): twenty for a million, thirty for a billion. The precondition is usually stated as 'the data must be sorted', and that is the special case of the real one. What binary search actually needs is a MONOTONIC PREDICATE: some yes-or-no question whose answers, read across the range, go no-no-no-yes-yes-yes and never flip back. Sortedness gives you that for free with the question 'is this item at least the target'. Once you see the general version, a whole class of problems that contain no array at all become binary searches.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles