Binary Search on the Answer

Ordinary binary search hunts for a value *inside* a sorted array. Binary search on the answer turns that idea inside out: it searches the range of possible answers directly. It works whenever you can write a yes/no test — a predicate — that flips exactly once: false for every candidate below some boundary, then true for every candidate above it (or the reverse). Testing the middle of the range tells you which side the boundary is on, so each test throws away half the candidates.

Worked example — least capacity to ship in D days

Packages of weights [1,2,3,4,5,6,7,8,9,10] must ship in order within D = 5 days on one boat. A larger boat capacity means fewer days, so feasible(cap) — *can we finish in ≤ 5 days with this capacity?* — is monotonic: false for small capacities, true for large ones. We binary-search the smallest capacity that still passes.

1. 1Bounds: capacity must be at least max(weights) = 10 (or the heaviest package never fits) and at most sum = 55 (ship everything in one day). So lo = 10, hi = 55.
2. 2mid = 32 → feasible (easily under 5 days), so the answer is ≤ 32: set hi = 32.
3. 3mid = 21 → feasible (3 days), set hi = 21.
4. 4mid = 15 → feasible (exactly 5 days), set hi = 15.
5. 5mid = 12 → infeasible (needs 6 days), so 12 is too small: set lo = 13.
6. 6mid = 14 → infeasible (6 days), set lo = 15. Now lo == hi == 15 — that boundary is the answer.

function shipInDays(weights, D) {
  let lo = Math.max(...weights);              // must fit the heaviest package
  let hi = weights.reduce((a, b) => a + b, 0); // one day for everything

  const feasible = (cap) => {
    let days = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { days++; load = 0; } // start a new day
      load += w;
    }
    return days <= D;
  };

  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (feasible(mid)) hi = mid;   // mid works -> answer is mid or smaller
    else lo = mid + 1;             // mid too small -> go higher
  }
  return lo; // smallest capacity that ships in D days -> 15
}