Binary Search on the Answer

1. The reframe

Binary search does not search arrays. It searches a monotone decision.

Koko asks for the minimum integer speed. Instead of guessing the formula for that speed, define:

works(speed) = total hours needed at this speed <= h

As speed increases, required hours never increase. The candidates look like:

false false false true true true
                  ^ first feasible answer

Find that boundary.

2. The four-part derivation

Before writing a loop, answer:

1. Candidate: what number am I searching? Speed, capacity, distance, days, maximum load?
2. Predicate: can I check one candidate in O(n) or better?
3. Monotonicity: why can the predicate switch only once?
4. Bounds: what smallest and largest candidates provably contain the answer?

If any sentence is missing, the binary search is not ready to code.

3. Minimum feasible template

long long l = minimumCandidate, r = maximumCandidate;
while (l < r) {
    long long mid = l + (r - l) / 2;
    if (works(mid)) r = mid;
    else l = mid + 1;
}
return l;

let l = minimumCandidate, r = maximumCandidate;
while (l < r) {
  const mid = l + Math.floor((r - l) / 2);
  if (works(mid)) r = mid;
  else l = mid + 1;
}
return l;

The feasible mid stays because it may be the first feasible candidate. A failed mid is removed with mid + 1 because it and everything smaller fail.

4. Koko’s predicate

For speed k, one pile of p bananas needs ceil(p / k) hours. Sum that over all piles.

long long hours = 0;
for (int pile : piles) hours += (pile + k - 1) / k;
return hours <= h;

const hours = piles.reduce((sum, pile) => sum + Math.ceil(pile / k), 0);
return hours <= h;

The predicate costs O(n); binary search calls it O(log M) times, where M is the largest pile. Total: O(n log M).

5. Common variants

• Minimum ship capacity to finish within D days.
• Minimum speed to arrive on time.
• Smallest divisor under a threshold.
• Maximum minimum distance between placed items: usually a maximum feasible boundary.
• Minimum possible largest subarray sum.

The stories differ; candidate, predicate, monotonic proof, and bounds are the same four boxes.

6. Traps

1. Guessing bounds such as 0..1e9 when proof gives tighter ones.
2. Starting a divisor or speed at zero.
3. Using floating-point ceiling in C++ when (p + k - 1) / k is exact.
4. Writing an expensive predicate and forgetting total complexity is predicate × log(range).
5. Searching for minimum feasible with the maximum-feasible update rules.

7. Blank derivation prompt

Packages must ship in order within D days. Without writing code, define the candidate, predicate, monotonic direction, lower bound, and upper bound. If all five are precise, implementation is mechanical.