What it is
Binary search repeatedly cuts a search space in half by testing its midpoint, discarding the half that can't contain the answer. It needs the space to be monotonic: some condition that's false, then true (or vice versa) as you move across it, whether that space is literally a sorted array or something more abstract like "every possible eating speed" or "every possible time value." Each iteration removes half the remaining candidates, so it reaches a single answer in logarithmic time even over a search space of billions.
When it applies
- The data is sorted, or the array has been rotated but still preserves a monotonic split you can identify from the endpoints.
- You're not looking for a value in an array at all, but for the smallest (or largest) number satisfying some yes/no condition that flips exactly once as the number increases — this is "binary search on the answer," and the array being sorted is irrelevant; what matters is that a feasibility check is monotonic.
- You need a boundary — the first or last position where something is true — rather than any single match.
- On an array that isn't sorted and has no other monotonic structure, binary search doesn't apply at all, even if you're searching for "the smallest value that satisfies X" — check that the feasibility function is actually monotonic before reaching for this pattern, or you'll get a wrong answer that still runs fast.
Tells in the problem
- "Sorted array," "rotated sorted array," or a matrix sorted along both rows and columns.
- An explicit requirement for logarithmic time when a linear scan or full sort would be the obvious first idea.
- "Return the smallest/largest value such that..." over a numeric range (a speed, a capacity, a time), which is often binary search on the answer rather than on an array.
- Repeated queries against data that doesn't change between queries, making a one-time sorted structure worth building.
- "First and last occurrence" or "insertion position" phrasing, which asks for a boundary rather than an exact index.
The classic mistake
Using mid = (lo + hi) // 2 with hi = mid instead of hi = mid - 1 (or the reverse) is the classic way to get the loop bounds or midpoint update wrong in a way that either infinite-loops or off-by-one skips the answer, when the update doesn't match the invariant being maintained. This happens because there are several valid binary-search templates (closed range vs. half-open, searching for a value vs. searching for a boundary) and mixing pieces from two of them produces code that looks plausible but loops forever on a two-element array. Catch it by writing down, before coding, exactly what lo and hi mean at each point ("the answer is somewhere in [lo, hi]" or "[lo, hi)") and keeping every update consistent with that statement.
Questions to start with
- Binary Search — the textbook template on a plain sorted array; get the loop invariant right here first.
- Find First and Last Position of Element in Sorted Array — searching for a boundary instead of any match, the next building block.
- Search in Rotated Sorted Array — the monotonic structure is hidden in a rotation, so you decide which half is sorted before recursing.
- Koko Eating Bananas — the pivot to binary search on the answer: no array is being searched, a feasibility check is.
- Median of Two Sorted Arrays — combines a partition search across two arrays at once, the hardest variant in this hub.