Binary Search on the Answer

MNEMONIC Bisect the answer, not the array.

PATTERN Binary search over a value range

Many optimization problems have no sorted array to search — but the answer itself lives in an orderable range, and a yes/no test on candidate answers is monotone. Instead of trying every candidate (an O(range) scan), you binary-search the range [lo, hi] for the boundary where feasible flips.

The loop invariant is identical to ordinary binary search: at every step the answer (if it exists) lies in [lo, hi]. Every boundary update must preserve it. What changes is the “comparison” — it's a whole-problem feasibility check, not an array lookup.

KEY IDEA The monotone predicate is the whole game

The technique is valid iff feasible(x) is monotone: there is exactly one value where it flips. Formally, for a min-feasible search: feasible(x) ⇒ feasible(x + 1) for all x in range.

• Koko: faster speed never needs more hours → hours ≤ h is monotone in speed.
• Ship within D days: bigger capacity never needs more days.
• Integer sqrt: x*x ≤ n is true for small x, false for large — a clean true→false flip.

Once you can articulate the monotonicity, the rest is the standard first-true (or last-true) bisection.

COST What it buys you

Total cost is O(log(hi − lo) × cost-of-feasible). For Koko, feasible is O(n) over the piles, so the whole thing is O(n · log(max(piles))) — far below the O(max(piles) · n) brute force.

VARIANT min-feasible vs max-feasible

Two mirror images, and getting the wrong one is the #1 source of off-by-one bugs:

• min-feasible (F…F | T…T, find first true): mid rounds down; feasible(mid) true → hi = mid, else lo = mid + 1; return lo.
• max-feasible (T…T | F…F, find last true): mid rounds up (+1 in the shift) to avoid an infinite loop; feasible(mid) true → lo = mid, else hi = mid - 1; return lo.

RUN IT Bisect the answer line

1function minEatingSpeed(piles: number[], h: number): number {
2▶  let lo = 1;                          // slowest conceivable speed
3▶  let hi = Math.max(...piles);         // fastest useful speed
4  while (lo < hi) {                    // invariant: answer in [lo, hi]
5    const mid = lo + ((hi - lo) >> 1); // probe a candidate speed
6    if (feasible(piles, h, mid)) {     // can finish in time at speed mid?
7      hi = mid;                        //   yes -> mid might be the answer, keep it
8    } else {
9      lo = mid + 1;                    //   no  -> too slow, must go faster
10    }
11  }
12  return lo;                           // smallest speed where feasible flips true
13}
14 
15function feasible(piles: number[], h: number, speed: number): boolean {
16  let hours = 0;
17  for (const p of piles) hours += Math.ceil(p / speed);
18  return hours <= h;                   // monotone: faster speed never needs more hours
19}

TRIGGERS When you see ___ → reach for ___

Reach for binary-search-on-the-answer when the problem asks for an extremal value (a min or a max), brute-forcing every candidate would be too slow, and you can write a yes/no feasibility test that is monotone in that value.

RED FLAGSWhen it's NOT this pattern

• The predicate is not monotone. If “feasible at x” can be true, then false, then true again across the range, there is no single boundary — this technique silently returns the wrong answer. Prove the one flip first.
• You want an exact element in an array, not an optimal value.That's plain binary search on an index — use the index template, with lo/hi as positions, not values.
• The objective is a window over a contiguous run.If the problem is “shortest/longest contiguous subarray meeting a condition,” a sliding window is usually O(n) and beats an O(n log n) bisect — see Minimum Size Subarray Sum in the Problems tab.

TEMPLATE Generic min-feasible bisection

When → You want the smallest value satisfying a monotone condition. Fill in feasible() — that stub is where the actual problem lives.

// Generic "smallest x with feasible(x) true" bisection.
// The predicate must be MONOTONE: false…false…TRUE…TRUE (one flip, never re-toggles).
function minFeasible(lo: number, hi: number): number {
  // lo = smallest candidate answer, hi = a value you KNOW is feasible.
  while (lo < hi) {                    // invariant: the answer lives in [lo, hi]
    const mid = lo + ((hi - lo) >> 1); // midpoint, can't overflow, rounds down
    if (feasible(mid)) {
      hi = mid;                        // mid works → it might BE the answer, keep it
    } else {
      lo = mid + 1;                    // mid fails → answer is strictly larger
    }
  }
  return lo;                           // lo === hi: the first x where feasible flips true
}

// Replace with the problem-specific check. This is where 90% of the work lives.
function feasible(mid: number): boolean {
  return true;
}

// For "largest x with feasible(x) true" (feasible is true…true…FALSE…false), flip it:
//   while (lo < hi) { const mid = lo + ((hi - lo + 1) >> 1);  // round UP
//                     if (feasible(mid)) lo = mid; else hi = mid - 1; }
//   return lo;

TEMPLATE Koko-style rate search

When → The answer is a rate (speed, capacity, throughput) and feasible(rate)simulates a greedy pass: “at this rate, does the job finish within the limit?”

// Koko Eating Bananas (LC 875) — binary-search the RATE.
// "Smallest eating speed k that finishes all piles within h hours."
function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;                          // slowest conceivable speed
  let hi = Math.max(...piles);         // no point eating faster than the biggest pile
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (hoursAt(piles, mid) <= h) {    // feasible: can finish in time at this speed
      hi = mid;                        //   yes → try slower
    } else {
      lo = mid + 1;                    //   no  → must go faster
    }
  }
  return lo;
}

// hours needed at a given speed — Σ ceil(pile / speed). Monotone DECREASING in speed,
// so "hours <= h" is monotone INCREASING (false for slow speeds, true for fast ones).
function hoursAt(piles: number[], speed: number): number {
  let hours = 0;
  for (const p of piles) hours += Math.ceil(p / speed);
  return hours;
}

TEMPLATE Integer sqrt / value bisection

When → A pure numeric search with no array at all: find the largest x with x·x ≤ n (or similar true→false predicate). This is the max-feasible mirror.

// Integer sqrt (LC 69) — value bisection with a non-array predicate.
// "Largest x such that x*x <= n."  feasible(x) = (x*x <= n) is true…true…FALSE.
function mySqrt(n: number): number {
  if (n < 2) return n;
  let lo = 1, hi = n;                  // answer ∈ [1, n]
  while (lo < hi) {
    const mid = lo + ((hi - lo + 1) >> 1);   // round UP for the max-feasible variant
    if (mid <= n / mid) {              // == mid*mid <= n, but NEVER overflows
      lo = mid;                        // mid is feasible → it might be the largest, keep it
    } else {
      hi = mid - 1;                    // mid too big → shrink
    }
  }
  return lo;                           // largest x with x*x <= n
}

PITFALL Searching the index range instead of the value range

The defining mistake of this technique: initializing lo/hi to 0 and arr.length - 1 when they should be values — e.g. 1 and max(piles), or max(arr) and sum(arr). Always ask “what unitare my bounds in?” You are bisecting the answer space, not array positions.

PITFALL Off-by-one: which side keeps mid?

For min-feasible (first true): when feasible(mid) is true, mid might be the answer, so write hi = mid — never hi = mid - 1, which would throw away the answer. When false, mid is ruled out, so move past it: lo = mid + 1.

For max-feasible (last true), mirror it: true → lo = mid, false → hi = mid - 1, and round mid up (lo + ((hi - lo + 1) >> 1)) or the loop never terminates at a two-element window.

PITFALL Assuming monotonicity that isn't there

Binary search on the answer is only correct when feasible()is genuinely monotone over the searched range. Convince yourself with one sentence (“more capacity is never worse”). If the predicate can flip back, the bisect deletes a half that may contain the true answer and returns nonsense — with no error to warn you.

PITFALL Overflow in the feasibility math

The midpoint is safe (lo + ((hi - lo) >> 1)), but the predicate can overflow: mid * mid for integer sqrt, or a running sum that exceeds MAX_INT. Prefer division forms (mid ≤ n / mid) or 64-bit accumulators. In TS/JS numbers are 64-bit floats so overflow is rare, but adopt the habit for the languages where it bites.

PROBLEMS