Learning/Binary Search

Binary Search

7 questions. The most templated section in the 150 — and the one where a single off-by-one silently turns a correct idea into an infinite loop.

The one idea

Most people learn binary search as "search a sorted array". That framing is too narrow, and it's why the harder variants feel like different problems. The real definition:

There is a predicate that is false, false, …, false, true, true, …, true over some ordered space, and you want the boundary.

The false-then-true predicate band and its boundary
The false-then-true predicate band and its boundary

Each step you test the middle. The result tells you which half the boundary is in, so you discard the other half. Halving repeatedly gives log₂ n steps: 20 for a million elements, 30 for a billion.

How the space collapses

Binary search narrowing the search space
Binary search narrowing the search space

Each step throws away half of what remains — so the saving compounds.

The three uses in this section

1. Search an index space — the classic, plus rotated variants. (Q1, Q2, Q4, Q5, Q6)

2. Search an answer space — the array isn't what you search; the candidate answers are. (Q3)

Koko Eating Bananas searches eating speeds rather than array elements: speed 1, 2, 3 are too slow, 4 and above all work. The boundary — the slowest speed that fits — is the answer.

3. Search a partition — you're looking for where to cut, not for a value. (Q7)

Easy Binary Search LC 704 9 min Medium Search a 2D Matrix LC 74 11 min Medium Koko Eating Bananas LC 875 11 min Medium Find Minimum in Rotated Sorted Array LC 153 10 min Medium Search in Rotated Sorted Array LC 33 11 min Medium Time Based Key-Value Store LC 981 12 min Hard Median of Two Sorted Arrays LC 4 16 min

The two conventions — pick one and never mix them

Almost every binary search bug is a mismatch here.

BoundsLoop conditionUpdateshi starts at
Inclusive [lo, hi]lo <= hilo = mid+1, hi = mid-1n - 1
Half-open [lo, hi)lo < hilo = mid+1, hi = midn

What goes wrong when you mix them:

The overflow trap

Java
int mid = (lo + hi) / 2;          // ✗ overflows when lo + hi > 2^31 - 1
int mid = lo + (hi - lo) / 2;     // ✓ only ever computes a difference

lo + hi can exceed the int range and wrap negative, indexing outside the array. This exact bug sat in the JDK's own Arrays.binarySearch for nine years — interviewers know the story and notice the safe form.

Prerequisites from Part 1

10 Binary Search the pattern summary this section instantiates01 Complexity & Problem Triage reading a constraint like 10^9 as "search the answer, not the array"02 Java Collections Toolkit §3 — TreeMap.floorEntry is the production answer to Q603 Java Syntax Mechanics integer overflow

Debugging checklist

When it loops forever or is off by one, check in this order:

  1. Do the loop condition and the pointer updates belong to the same convention? This is the cause about 80% of the time.
  2. Can a pointer fail to move on some branch? hi = mid is safe only with lo < hi, because mid < hi is then guaranteed.
  3. Is mid computed as lo + (hi - lo) / 2?
  4. Is the predicate genuinely monotonic over the search space? If not, binary search is the wrong tool and no amount of index fixing will save it.

How to work this section

  1. Read §1 and §2 only, then attempt cold with a timer — 20 min Easy, 35 Medium, 45 Hard.
  2. After the attempt, read §3 and §4 and diff against your reasoning.
  3. Use the counter-questions in §3 as a quiz — for each approach, cover the answers and defend it yourself.
  4. Read §7 last: the modified-constraint variants.

Write the convention down before you code. Deciding "inclusive bounds, lo <= hi, mid ± 1" first prevents the entire class of bugs above.

What to carry forward