Binary Search on the Answer: Searching a Range of Values

Binary search on the answer applies binary search not to an array, but to the range of possible answers. When a problem asks you to minimize or maximize some value, and you can cheaply check “is value x feasible?”, and feasibility flips just once (false → true) as x grows, you can binary-search that boolean line to find the optimal value in O(log(range) × check) time. It’s one of the highest-leverage techniques in competitive programming and interviews.

The shape of these problems

Three ingredients have to be present:

You’re optimizing a value — “smallest capacity”, “minimum speed”, “largest minimum distance”.
A feasibility test feasible(x) you can compute, usually in O(n).
Monotonicity: if some x works, then everything on one side of it also works. The answers look like false, false, false, true, true, true — a single flip.

When that holds, finding the boundary between “doesn’t work” and “works” is exactly lower_bound — but over a value range instead of an array.

For beginners: The mental shift: instead of asking “what is the answer?”, you ask “could the answer be x?” — a yes/no question that’s far easier. Then you binary-search for the smallest yes.

Worked example: Koko Eating Bananas

Koko has piles[] of bananas and h hours before the guards return. Each hour she picks one pile and eats up to k bananas from it (if the pile has fewer, she eats it and waits out the hour). Find the minimum eating speed k so she finishes all piles within h hours.

Step 1 — bound the answer. The slowest sensible speed is k = 1. The fastest she’d ever need is k = max(piles) (one pile per hour). So the answer is in [1, max(piles)].

Step 2 — feasibility check. At speed k, pile p takes ceil(p / k) hours. Total hours = sum of those. feasible(k) is totalHours <= h. A bigger k never increases the hours — that’s the monotonicity (false … false true … true).

Step 3 — binary-search the smallest feasible k using the half-open lower-bound template.

long long hoursNeeded(const std::vector<int>& piles, long long k) {
    long long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;   // ceil(p / k)
    return hours;
}
int minEatingSpeed(const std::vector<int>& piles, int h) {
    int lo = 1, hi = *std::max_element(piles.begin(), piles.end());
    while (lo < hi) {                       // search smallest feasible k
        int mid = lo + (hi - lo) / 2;
        if (hoursNeeded(piles, mid) <= h) hi = mid;   // feasible, try slower
        else lo = mid + 1;                            // too slow, speed up
    }
    return lo;
}

long hoursNeeded(int[] piles, long k) {
    long hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;   // ceil(p / k)
    return hours;
}
int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {                       // search smallest feasible k
        int mid = lo + (hi - lo) / 2;
        if (hoursNeeded(piles, mid) <= h) hi = mid;   // feasible, try slower
        else lo = mid + 1;                            // too slow, speed up
    }
    return lo;
}

function hoursNeeded(piles, k) {
  let hours = 0;
  for (const p of piles) hours += Math.ceil(p / k);
  return hours;
}
function minEatingSpeed(piles, h) {
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {                        // search smallest feasible k
    const mid = lo + Math.floor((hi - lo) / 2);
    if (hoursNeeded(piles, mid) <= h) hi = mid; // feasible, try slower
    else lo = mid + 1;                          // too slow, speed up
  }
  return lo;
}

import math

def hours_needed(piles, k):
    return sum(math.ceil(p / k) for p in piles)

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:                          # search smallest feasible k
        mid = lo + (hi - lo) // 2
        if hours_needed(piles, mid) <= h:
            hi = mid                        # feasible, try slower
        else:
            lo = mid + 1                    # too slow, speed up
    return lo

For piles = [3, 6, 7, 11], h = 8, this returns 4: at speed 4 the hours are 1 + 2 + 2 + 3 = 8 ≤ 8, and speed 3 would need 1 + 2 + 3 + 4 = 10 > 8.

Complexity

Time: O(n · log(maxPile)). Each feasibility check is O(n), and we do log(maxPile) of them.
Space: O(1) beyond the input.

Compare that to trying every speed from 1 upward — O(n · maxPile). The binary search collapses the answer range logarithmically.

A reusable template

Almost every “minimize the maximum / maximize the minimum” problem fits this mould:

lo, hi = smallest possible answer, largest possible answer
while lo < hi:
    mid = lo + (hi - lo) / 2
    if feasible(mid):  hi = mid        # minimizing -> keep mid, shrink right
    else:              lo = mid + 1
return lo

To maximize instead, flip the check so feasibility runs true … true false … false, and search for the largest true. Other classics with the same skeleton: minimum ship capacity to ship in D days, split array into k subarrays minimizing the largest sum, and aggressive cows / maximize minimum distance.

Pitfall: The technique is only valid if feasibility is monotonic. Always prove (even informally) that “if x works, x+1 works” — otherwise binary search can land on a wrong value. Also watch for overflow when summing hours or sizes: use 64-bit accumulators (long/long long).

Going deeper: This is the most powerful member of the binary search pattern family. Recognizing the words “minimum/maximum such that…” plus a monotonic check is the trigger to reach for it.

Next: put it all together with the searching exercises and solutions.