Binary search on the answer

The strongest use of binary search has no sorted array in sight. If you can write a check isFeasible(x) that is monotonic — false, false, false, true, true, true — then you can binary search the answer space itself.

The shape

"Ship all packages within D days. Find the smallest ship capacity."

Capacity is monotonic: if capacity 20 works, 21 works. If 19 fails, 18 fails. So search capacities.

function shipWithinDays(weights, days) {
  const feasible = (capacity) => {
    let used = 1;
    let load = 0;

    for (const w of weights) {
      if (load + w > capacity) { used++; load = 0; }
      load += w;
    }

    return used <= days;
  };

  let lo = Math.max(...weights);              // cannot split one package
  let hi = weights.reduce((a, b) => a + b);   // everything in one day

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (feasible(mid)) hi = mid;              // keep mid: it might be the best
    else lo = mid + 1;
  }

  return lo;
}

O(n log(sum)) — a handful of passes rather than a search over every capacity.

The three things to get right

1. Establish monotonicity. If feasibility flips back and forth, binary search is invalid. Say why it is monotone before you write code.
2. Set the bounds to the tightest values you can justify. lo is the smallest conceivable answer, hi the largest.
3. Use the lower-bound template. hi = mid when feasible, lo = mid + 1 when not, and the loop lands on the smallest feasible value.

For a maximum rather than a minimum, mirror it: lo = mid when feasible, and take mid on the upper half — with mid = lo + ceil((hi - lo) / 2) to avoid an infinite loop.

Recognising it

The tell is a question asking for a minimum maximum or maximum minimum: "minimise the largest sum", "maximise the smallest distance", "smallest divisor given a threshold", "Koko eating bananas", "split array largest sum". Those all reduce to: guess an answer, verify it in linear time, halve the guess range.

Binary search on the answer converts "find the optimum" into "check a candidate", which is nearly always the easier problem.