Binary Search: More Than Looking Up a Sorted Array

Everyone can describe binary search in a sentence: check the middle, throw away half. Then they open an editor and spend twenty minutes fighting an infinite loop or an off-by-one. That gap — trivial to explain, fiddly to get right — is what this hub is about, along with the reframe that unlocked most of the harder NeetCode problems for me: binary search isn’t really about sorted arrays.

It isn’t about sorted arrays

The sorted array is just the most common place you can ask “am I too high or too low?” and trust the answer. What binary search actually needs is a monotonic predicate: some yes/no question where, once the answer flips, it stays flipped. arr[mid] >= target is monotonic across a sorted array. But so is git bisect when you’re hunting a regression that stays broken once it appears — every commit after the first bad one fails the same test — which is why bisecting a thousand commits takes about ten builds, not a thousand. Same idea, no array in sight.

Hold onto that framing. Half of the “medium” binary search problems are just a monotonic predicate hiding behind a story, and spotting the predicate is the whole trick.

The part everyone gets wrong: the boundaries

Here’s the exact-match template I’ve settled on, with inclusive bounds:

int lo = 0, hi = arr.length - 1;   // both ends are valid indices
while (lo <= hi) {                 // <=, because lo == hi is still one live cell
    int mid = lo + (hi - lo) / 2;  // not (lo + hi) / 2 — that overflows once lo + hi exceeds int range
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) lo = mid + 1;   // discard mid and everything left
    else hi = mid - 1;                           // discard mid and everything right
}
return -1;

Four decisions cause every binary search bug I’ve ever written, and they all have to agree with each other:

• Inclusive or exclusive hi? Here hi is a real index, so it starts at length - 1.
• lo <= hi or lo < hi? With inclusive bounds you need <=, or you skip the last cell when lo == hi.
• mid + 1 / mid - 1, or plain mid? Because I check mid before moving, I can safely exclude it. Templates that move hi = mid must keep mid in play, or they loop forever.
• How is mid computed? lo + (hi - lo) / 2 avoids the integer overflow that (lo + hi) / 2 hits once the array is large.

Pick one consistent set and stop improvising. Almost every “binary search is so buggy” story is really “I mixed an inclusive template with an exclusive loop condition.”

Searching on the answer

This is where the sorted array disappears entirely. When a problem asks for the smallest value that still works and “works” only gets easier as the value grows, you can binary-search the answer space directly, hunting the first value that passes. (The mirror case — the largest value that still works, where “works” fails once the value grows too far — flips the predicate and hunts the last passing value instead.)

Take Koko Eating Bananas: given piles and a deadline of h hours, find the slowest eating speed that still clears every pile in time. There’s no sorted array to index — but the predicate “can Koko finish at speed k?” is monotonic: faster is always at least as good. So you binary-search k over 1 .. max(pile), and the check is a quick sum of ceil(pile / k) hours:

int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
while (lo < hi) {                 // finding a boundary: lo < hi, hi = mid keeps mid live
    int k = lo + (hi - lo) / 2;
    if (canFinish(piles, k, h)) hi = k;   // k works → maybe a slower speed also works
    else lo = k + 1;                       // too slow → speed up
}
return lo;                        // smallest k that finishes in time

Notice the template changed: lo < hi now, and hi = mid instead of mid - 1, because I’m no longer checking for equality — I’m hunting the boundary between “fails” and “works.” That’s the second template worth owning, and it’s the one that turns capacity questions into a handful of trials instead of a linear crawl — “smallest server pool that keeps p99 under the SLA,” as long as latency really does fall as you add capacity.

The rotated-array twist

Rotated-array problems are the interview favorite because they break the one assumption binary search leans on — global sortedness — and make you rebuild it locally. A rotated array still has the property that at least one half of any [lo, hi] window is sorted, so each step you figure out which half is clean, decide whether the target lives in it, and recurse into the right side. Two problems on this site work it end to end:

• Search in Rotated Sorted Array — find a target by detecting the sorted half each step.
• Find Minimum in Rotated Sorted Array — the same idea aimed at the rotation pivot instead of a value.

The other NeetCode binary-search problems layer these ideas: 704 and 74 are straight lookups (74 just flattens a matrix into one virtual sorted array), 981 binary-searches timestamps, and Median of Two Sorted Arrays is the famously nasty one — a binary search over partitions rather than elements. I’ll write those up as I get to them.

Just how fast is that?

Fast enough that a sorted list of four billion items is about 32 comparisons. If you want the actual derivation — why halving the range gives $\log_2 n$ and how it stacks up against a linear scan — I worked through the math separately in Why is Binary Search O(log n)?. For this hub it’s enough to know that each comparison halves what’s left, so the cost grows by one step every time the input doubles.

Own two templates, not ten

I stopped collecting binary-search snippets once I had these two: the inclusive exact-match loop for “is this value here,” and the exclusive boundary loop for “smallest value that works.” Every problem above is one of those two with a different predicate plugged in. When a new problem shows up, I don’t ask “how do I binary-search this array” — I ask “what’s the monotonic yes/no question, and which of my two templates finds its edge.” Get the predicate right and the boundaries stop biting.

References

• NeetCode 150 — Binary Search — the source list for this hub.
• Why is Binary Search O(log n)? — the complexity derivation.