Binary Search on the Answer

When the search space is a range of possible answers rather than an array index, binary search on the answer space converts hard optimization problems into O(log(range)) predicate checks.

5 min read Level 3/5 #dsa#searching#binary-search

What you'll learn

Identify problems where the answer space is monotone and binary-searchable
Write a boolean predicate that tests whether a candidate answer is feasible
Apply the pattern to a classic resource-allocation problem (koko bananas style)

Classic binary search finds a value in a sorted array. Binary search on the answer flips the idea: instead of searching an array, you search a range of candidate answers and for each candidate ask “is this feasible?”

The Key Insight

If you can express the problem as a monotone predicate — meaning there exists some threshold k such that canAchieve(x) is false for all x < k and true for all x >= k — then binary search on the answer finds k in O(log(range)) predicate evaluations.

The invariant is identical to classic binary search:

lo always points to a value that is too small (or is the lower bound).
hi always points to a value that is large enough (feasible).

When lo === hi you have found the minimum feasible answer.

Worked Example: Minimum Eating Speed (Koko Bananas)

A monkey must eat all bananas in h hours. There are piles of bananas. Each hour the monkey picks one pile and eats up to k bananas from it. Find the minimum k such that all piles can be finished in h hours.

Brute-force tries every k from 1 upward — O(max(piles) * n). Binary search on k reduces this to O(n log(max(piles))).

function minEatingSpeed(piles, h) {
  // Predicate: can the monkey finish everything at speed k?
  function canFinish(k) {
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / k);
    }
    return hours <= h;
  }

  let lo = 1;                      // minimum conceivable speed
  let hi = Math.max(...piles);     // eating the largest pile in one hour always works

  // Invariant: canFinish(hi) is always true, canFinish(lo - 1) is always false
  while (lo < hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);
    if (canFinish(mid)) hi = mid;  // mid works — try smaller
    else                lo = mid + 1; // mid too slow — go higher
  }

  return lo; // minimum speed that satisfies the constraint
}

minEatingSpeed([3, 6, 7, 11], 8); // 4
minEatingSpeed([30, 11, 23, 4, 20], 5); // 30

Complexity

Step	Cost
Predicate check	O(n)
Binary search iterations	O(log(max(piles)))
Total	O(n log(max(piles)))

Template

Most binary-on-answer problems follow this exact template:

function solveMinimum(/* problem inputs */) {
  function feasible(candidate) {
    // return true if candidate satisfies the constraint
  }

  let lo = MINIMUM_POSSIBLE_ANSWER;
  let hi = MAXIMUM_POSSIBLE_ANSWER;

  while (lo < hi) {
    const mid = Math.floor(lo + (hi - lo) / 2);
    if (feasible(mid)) hi = mid;
    else               lo = mid + 1;
  }

  return lo;
}

For maximum problems (find the largest feasible value) swap the branches: if (feasible(mid)) lo = mid; else hi = mid - 1; and start hi at a known upper bound.

Recognizing the Pattern

Ask yourself three questions:

Can I define “feasible” (or “achievable”) for a single candidate value?
If x is feasible, is every x' > x also feasible (monotone)?
Is the answer range bounded so I can set lo and hi?

If all three are yes, binary search on the answer applies.

Up Next

What if the array has no known upper bound? Exponential search first locates the search window, then hands off to binary search.

Exponential Search →