Binary Search on Answers

Classic binary search finds a value in a sorted array. Binary search on answers finds the smallest x such that some predicate ok(x) is true, when ok is monotonic: once it becomes true, it stays true.

That covers a shocking amount of contest problems: minimum capacity to ship packages, first day you can make m products, smallest maximum edge on a path, cutting wood, aggressive cows…

Lower bound on a boolean array — the only binary search you needjs

// ok[i] is false* then true*. Return first index where ok(i) is true.
function firstTrue(lo, hi, ok) {
  // search in [lo, hi), invariant: ok(lo-1) is false, ok(hi) is true
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

TRACE

Find the first true in [F, F, F, T, T, T]. Indices 0…5.

lo = 0, hi = 6

mid = 3. ok(3) = T, so the first true is at 3 or left. hi = 3.

true → hi = mid

1 / 4

CHECK

You want the minimum speed s so that you finish eating piles[] bananas in h hours (Koko). Why binary search s?

To use the pattern in the wild:

1. Phrase the answer as a number x on a known range. 2. Write ok(x) so it is true iff x is feasible. 3. Prove: ok(x) implies ok(x+1) (or the opposite, and search the last true). 4. Binary search. Check ok at mid by simulating — often a greedy O(n) pass. 5. Total time O(n log X) where X is the value range (often 10⁹ or 10¹⁸).

CHECK

ok(x) is 'true, true, false, false.' Can you binary search for the first false?

Checks 0/2

Next lesson