A lesson from the Algorithms & Patterns module of the bootcamp. About a 12 minute read.
Halve the search range, repeat, and a million items take about twenty steps. Everybody can describe binary search, yet when Jon Bentley had professional programmers write it, about nine in ten versions had a bug, and one bug sat in a standard library for nine years. The idea is trivial. The boundaries are not. 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 it is too big, the left half. Throw away the half that cannot contain it and repeat. Each step halves the range, so it takes log2(n) steps: twenty for a million, thirty for a billion. The requirement is usually stated as 'the data must be sorted', but that is a special case of the real one. What binary search actually needs is a MONOTONIC PREDICATE: a yes-or-no question whose answers, read across the range, go no, no, no, yes, yes, yes and never flip back. Sorted data 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 with no array in them at all turn into binary searches.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 576 practice puzzles