Binary search

The problem it solves

Somewhere in a sorted collection is (maybe) the thing you want. Scanning from the front works, but its cost grows with the collection: a million entries, up to a million looks. Binary search finds anything in a sorted million in at most twenty-one looks, and in a sorted trillion in about forty. Whenever data is sorted — or can be made to act sorted — linear scanning is leaving a logarithm on the table.

The quiet, more valuable version of this problem: you don’t have an array at all, you have a question that flips once. “What’s the smallest capacity that ships all these packages in five days?” As capacity grows, the answer goes from no-no-no to yes-yes-yes, exactly once. Any such monotonic yes/no boundary can be found by binary search over the answers themselves — no array required. A large fraction of medium interview problems are this pattern wearing a costume.

The intuition — and where it breaks down

It’s the number-guessing game. I think of a number between 1 and 100; you guess 50; I say “higher”; you guess 75. Each guess doesn’t just test one number — it eliminates half of all remaining numbers, because “higher” tells you something about every number below 50 at once. Sortedness is what lets one comparison speak for many elements: if a[50] is too small, then a[0] through a[49] are all too small, unexamined.

Where the analogy misleads: in the guessing game the number is definitely there. Real searches miss, and the miss path is where the bugs live — the range shrinks and shrinks and must become empty cleanly, without the loop running forever or reading off the end. The analogy also hides that “the middle” needs care: with integer indices, the midpoint of an even range rounds somewhere, and which way it rounds must agree with how the bounds move, or one specific range size loops forever.

Loading…

A walkthrough you can check

Search for 41 in [7, 12, 19, 25, 33, 41, 58, 76] (indices 0–7).

1. lo = 0, hi = 7, so mid = 3. a[3] = 25 < 41 — everything at index 3 or lower is eliminated in one comparison. lo becomes 4.
2. lo = 4, hi = 7, mid = 5. a[5] = 41 — found, three comparisons, and five of the eight elements were never looked at.

Now search for 40 in the same array: the first two probes go identically, then a[5] = 41 > 40 pulls hi down to 4, mid = 4 gives 33 < 40 pushing lo to 5 — and now lo > hi. The range is empty, the loop exits, and the algorithm reports absence with proof: every region that could have held 40 was eliminated. Run the visualization with a miss (about one in four seeded inputs searches for an absent value) and watch the range collapse to nothing.

The invariant

If the target exists at all, it lies between lo and hi inclusive. Every line of the loop exists to preserve that sentence. When a[mid] < target, indices up to and including mid cannot hold the target, so lo = mid + 1 keeps the invariant while shrinking the range. When the range empties, the invariant plus emptiness yields the conclusion: no such element.

The classic infinite loop comes from breaking the pairing between the loop condition and the updates. With while (lo < hi) and hi = mid (a lower-bound search), the midpoint must round down, or a two-element range never shrinks. With while (lo <= hi), updates must skip past mid on both sides (mid + 1, mid − 1). Mix the conventions and there is exactly one range size that cycles forever — which is why the bug survives light testing.

Complexity, derived

Each probe removes at least half of the remaining candidates (the midpoint itself always goes). Starting from n candidates, after k probes at most n / 2^k remain; the loop must end by the time that hits below 1, so k ≤ ⌈log₂ n⌉ + 1. The visualization enforces this as a test: on 1,000 elements, never more than 11 comparisons, and the trace’s step count is checked to grow logarithmically. Space is O(1) for the loop form — the recursive form spends O(log n) stack for no benefit and is worth writing iteratively on principle.

The subtlety Big-O hides: on modern hardware, binary search over a huge array is cache-hostile — each probe lands far from the last. For small arrays (a few dozen elements), a plain linear scan is often faster in wall-clock time. The logarithm wins asymptotically, not universally.

What people get wrong

(lo + hi) / 2 overflows. In fixed-width languages, lo + hi can exceed the integer maximum when both are large; lo + (hi − lo) / 2 cannot. In JavaScript the overflow doesn’t bite (doubles), but writing the safe form signals you know why it exists — this is a genuinely famous bug that lived in the JDK’s own binarySearch for years.

Returning mid when the problem wanted a boundary. “Find the first occurrence”, “find where to insert”, “find the smallest x such that…” all want the lower-bound variant: on a match, keep searching left instead of returning. Most real uses want a boundary, not a hit — internalize the lower-bound form and the plain form becomes the special case.

Searching unsorted data. The invariant is a theorem about sorted input. On unsorted data binary search returns confident nonsense, which is worse than failing.

Implementation notes across languages

Python ships the boundary forms directly: bisect.bisect_left is lower bound, bisect_right upper — using them beats hand-rolling in both correctness and speed. Java has Arrays.binarySearch, but its negative-value return encoding (-(insertionPoint) - 1) is a bug farm; decode it immediately or write your own boundary search. C++’s std::lower_bound/upper_bound are the canonical pair, and their naming is the cleanest mental model of the two variants. In JavaScript there is nothing in the standard library — you will write it by hand in interviews, which is exactly why interviewers love asking it.