Binary Search on Answer

Some problems don’t ask you to search for a value in an array — they ask you to search for the best number satisfying a condition, like “what is the minimum speed at which I can eat all these banana piles in time?” or “what is the smallest ship capacity that gets every package delivered within the deadline?” Binary search on the answer (also called binary search on the answer space or parametric search) solves exactly this class of problem: instead of binary searching over array indices, you binary search over the range of possible answers, using a yes/no feasibility check to decide which half of that range to keep. It turns problems that look like brute-force optimization into an O(log range) search, as long as one condition holds: the feasibility check must be monotonic.

Overview / How it works

Standard binary search assumes you already have a sorted array and you’re looking for a specific value inside it. Binary search on the answer generalizes the same idea one level up: instead of an array, you have a range of candidate answers [low, high], and instead of comparing arr[mid] to a target, you ask a yes/no question — “is this candidate answer feasible?” — and use the answer to shrink the range.

This only works if feasibility is monotonic across the range: once a candidate value becomes feasible, every larger (or every smaller, depending on the problem) value must also be feasible. Picture the range of candidates laid out in a line, with every infeasible one marked False and every feasible one marked True. Monotonicity means you never see a mixed pattern like True, False, True — the Falses and Trues must form two contiguous blocks, with the boundary between them being the answer you want.

Concretely, take the “Koko eats bananas” scenario: Koko has piles of bananas and h hours to eat them all, eating at a constant integer speed k bananas per hour. If speed k is fast enough to finish in time, any faster speed also finishes in time — that’s monotonic. So instead of trying every possible speed one at a time, you binary search over the speed: pick a candidate in the middle of the plausible range, check whether it’s fast enough (a simple pass over the piles), and throw away half the remaining speeds each time.

The general recipe has four parts:

1. Identify what you are searching for as a numeric answer (a speed, a capacity, a distance, a sum) rather than an index.
2. Determine a valid [low, high] range that is guaranteed to contain the answer.
3. Write a feasible(candidate) function that answers “does this candidate satisfy the constraints?” in a way that is monotonic across [low, high].
4. Binary search over [low, high] using that predicate, narrowing toward the boundary between infeasible and feasible.

Because you are searching for a boundary rather than an exact match, the loop is usually written with the invariant low < high (searching for the smallest feasible value, keeping high = mid when mid is feasible) rather than the low <= high invariant used in classic “find this exact value” binary search. Getting this invariant right is the single most important detail in this technique — the Common Mistakes section below covers what happens when you get it wrong.

Time and Space Complexity

Every iteration of binary search on the answer halves the size of the candidate range [low, high], exactly like ordinary binary search halves an array. If the range has R possible values, that takes O(log R) iterations. The difference from array binary search is that each iteration does real work: it runs the feasible(candidate) check, which costs whatever it costs for your specific problem — often O(n) to scan the input once. Multiply the two together and the total time is O(f(n) × log R), where f(n) is the cost of one feasibility check and R is the size of the answer range (high - low). Space is O(1) beyond the input, since the search itself only tracks a handful of integers (low, high, mid) and does not recurse or allocate extra structures.

Example	Feasibility check cost	Answer range size	Total time
Integer square root	O(1) — one multiplication and comparison	O(n)	O(log n)
Minimum eating speed (Koko)	O(m) — sum a ceiling division over m piles	O(max(piles))	O(m log(max(piles)))
Minimum ship capacity	O(m) — one greedy pass over m weights	O(sum(weights))	O(m log(sum(weights)))

In every case, space stays O(1) extra — the feasibility checks below use only a running total and a counter, no auxiliary arrays.

Examples

Example 1: Integer square root

The simplest illustration: computing floor(sqrt(n)) without using math.sqrt. The candidate answer is some integer mid; it’s feasible if mid * mid <= n. Feasibility is monotonic — if 5*5 <= 41 is true, so is 4*4 <= 41 — so we binary search for the largest feasible mid.

def integer_sqrt(n: int) -> int:
    if n < 2:
        return n
    low, high = 1, n
    result = 0
    while low <= high:
        mid = (low + high) // 2
        if mid * mid <= n:
            result = mid
            low = mid + 1
        else:
            high = mid - 1
    return result


def main() -> None:
    for n in [0, 1, 8, 15, 16, 100]:
        print(f"integer_sqrt({n}) = {integer_sqrt(n)}")


if __name__ == "__main__":
    main()

Output:

integer_sqrt(0) = 0
integer_sqrt(1) = 1
integer_sqrt(8) = 2
integer_sqrt(15) = 3
integer_sqrt(16) = 4
integer_sqrt(100) = 10

Trace it by hand for n = 15: the range starts at low = 1, high = 15. The midpoint 8 gives 8*8 = 64, greater than 15, so high becomes 7. Midpoint 4 gives 16 > 15, so high becomes 3. Midpoint 2 gives 4 <= 15 — feasible — so we record result = 2 and push low up to 3. Midpoint 3 gives 9 <= 15 — also feasible — so result = 3 and low becomes 4, at which point low > high and the loop ends. The last recorded feasible value, 3, is floor(sqrt(15)), matching the printed output.

Example 2: Minimum eating speed (Koko Eating Bananas)

Koko has piles of bananas and h hours before the guards return. She picks one integer speed k and eats at that speed all day: for any pile, if it has more than k bananas left she eats k that hour and returns next hour; otherwise she finishes the pile and doesn’t start another one that same hour. We want the minimum k that lets her finish everything within h hours.

The candidate answers are speeds from 1 to max(piles) (eating faster than the largest single pile never helps). Feasibility is “can Koko finish all piles within h hours at speed k?”, computed with math.ceil(pile / k) summed over every pile — monotonic, since a faster speed can only need the same or fewer hours.

import math


def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_needed(speed: int) -> int:
        return sum(math.ceil(pile / speed) for pile in piles)

    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if hours_needed(mid) <= h:
            high = mid
        else:
            low = mid + 1
    return low


def main() -> None:
    piles = [3, 6, 7, 11]
    h = 8
    print(f"minimum eating speed: {min_eating_speed(piles, h)}")


if __name__ == "__main__":
    main()

Output:

minimum eating speed: 4

With piles = [3, 6, 7, 11] and h = 8, the search starts at low = 1, high = 11. At mid = 6, hours needed are 1 + 1 + 2 + 2 = 6, within budget, so high drops to 6. At mid = 3, hours needed jump to 1 + 2 + 3 + 4 = 10, over budget, so low rises to 4. At mid = 5, hours needed are 1 + 2 + 2 + 3 = 8, exactly on budget, so high drops to 5. At mid = 4, hours needed are still 1 + 2 + 2 + 3 = 8, feasible, so high drops to 4, matching low, and the loop ends with answer 4.

Example 3: Minimum ship capacity within D days

A more realistic scenario: packages with fixed weights must be loaded onto a ship, in order, over days days, without splitting a package or reordering them. Given a capacity, a greedy simulation tells you the minimum days needed: keep loading packages onto the current day until the next one would exceed capacity, then start a new day. We want the smallest capacity that finishes within the deadline.

The candidate range is [max(weights), sum(weights)]: a capacity below the heaviest single package could never load that package, and capacity equal to the total weight always finishes in one day. Feasibility — “does this capacity finish within days days?” — is monotonic, since more capacity can only reduce or keep the same day count.

def ship_within_days(weights: list[int], days: int) -> int:
    def days_needed(capacity: int) -> int:
        days_used = 1
        current_load = 0
        for weight in weights:
            if current_load + weight > capacity:
                days_used += 1
                current_load = 0
            current_load += weight
        return days_used

    low, high = max(weights), sum(weights)
    while low < high:
        mid = (low + high) // 2
        if days_needed(mid) <= days:
            high = mid
        else:
            low = mid + 1
    return low


def main() -> None:
    weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    days = 5
    print(f"minimum capacity: {ship_within_days(weights, days)}")


if __name__ == "__main__":
    main()

Output:

minimum capacity: 15

This one is worth tracing partway. weights sums to 55 and the heaviest package is 10, so the search starts at low = 10, high = 55. Trying mid = 32 needs only 2 days — very feasible — so high collapses to 32. Trying mid = 15 needs exactly 5 days, still feasible, so high drops to 15. Trying mid = 12 needs 6 days — one too many — so low rises to 13. Trying mid = 14 still needs 6 days, so low rises to 15, matching high, and the loop ends at 15: any smaller capacity forces a sixth day, and 15 is exactly enough for five.

How it works step by step

To see the shrinking range explicitly, here is every iteration of min_eating_speed([3, 6, 7, 11], 8) from Example 2:

Iteration	low	high	mid	hours_needed(mid)	Feasible?	Update
1	1	11	6	6	Yes (6 <= 8)	high = 6
2	1	6	3	10	No (10 > 8)	low = 4
3	4	6	5	8	Yes (8 <= 8)	high = 5
4	4	5	4	8	Yes (8 <= 8)	high = 4

After iteration 4, low equals high (both 4), so the loop condition low < high is false and the search stops. The range shrinks from 11 candidate speeds down to a single answer in just 4 steps, instead of testing all 11 speeds one at a time. Notice high is only ever updated to mid (never mid - 1), because mid itself might be the true answer and discarding it would be wrong; low = mid + 1 is safe on the other branch because we’ve just proven mid is not feasible, so it cannot be the answer we want.

Common Mistakes

Mistake 1: Wrong loop invariant causes an infinite loop

A common bug is copying the “find an exact match” binary search template (while low <= high, with high = mid - 1) onto a boundary search without changing the update rule. Watch what happens when high is updated to mid but the loop condition stays low <= high:

low, high = 1, max(piles)
while low <= high:
    mid = (low + high) // 2
    if hours_needed(mid) <= h:
        high = mid          # BUG: when low == high == mid, high never shrinks
    else:
        low = mid + 1
return low

Once low and high converge to the same value, mid equals that value too. If hours_needed(mid) <= h is still true there (which it will be, at the true answer), the code sets high = mid — but high already equals mid, so nothing changes, and low <= high stays true forever. The fix is to change the loop condition to low < high, which stops the loop the instant low and high meet, before the no-op update can happen:

low, high = 1, max(piles)
while low < high:
    mid = (low + high) // 2
    if hours_needed(mid) <= h:
        high = mid
    else:
        low = mid + 1
return low

As a rule of thumb: when your update rule can set high = mid (keeping mid as a still-possible answer), pair it with while low < high. Only use while low <= high when both branches strictly shrink past mid (high = mid - 1 and low = mid + 1), which suits exact-match search, not boundary search.

Mistake 2: Picking a search range that isn’t actually valid

Binary search on the answer only works if every value in [low, high] could plausibly be the answer. It’s tempting to just start low at 1 “to be safe,” but if the feasibility check doesn’t explicitly reject impossible values, the predicate can silently misbehave:

low, high = 1, sum(weights)          # BUG: low should be max(weights)
while low < high:
    mid = (low + high) // 2
    if days_needed(mid) <= days:
        high = mid
    else:
        low = mid + 1
return low

The greedy days_needed simulation always loads at least one item per day, even a single package heavier than the ship’s capacity — it only checks whether adding an item would exceed the running total, never whether the item alone fits. So a capacity smaller than the heaviest package still gets a finite, misleadingly low day count back, which can make the search converge on a capacity that’s physically impossible. The fix is to only search within a range you can prove is valid — capacity must be at least max(weights), since anything smaller cannot carry the heaviest package no matter what the simulation reports:

low, high = max(weights), sum(weights)
while low < high:
    mid = (low + high) // 2
    if days_needed(mid) <= days:
        high = mid
    else:
        low = mid + 1
return low

Whenever you set up low and high, ask “is it actually possible for the answer to be outside this range?” and “is my feasibility check monotonic across the entire range, including the edges?” Skipping this check is the most common source of subtly wrong answers here — the code runs without crashing, but converges on the wrong number.

Best Practices

• Reach for binary search on the answer when a problem asks for a minimum or maximum numeric value satisfying a condition, and testing one candidate is much cheaper than deriving the answer directly.
• Before writing code, state the feasibility predicate in one sentence and convince yourself it’s monotonic across the whole range.
• Decide up front whether you want the smallest feasible value or the largest, and use the matching template consistently (while low < high with high = mid for smallest-feasible; the mirror image, low = mid, for largest-feasible, with mid computed as (low + high + 1) // 2 to avoid its own infinite loop).
• Double-check that low and high are both individually valid, achievable bounds — not just “small enough” and “big enough” guesses.
• Keep the feasibility check pure (no shared mutable state between calls), which is what monotonicity actually requires.
• Remember the total cost is feasibility check cost × log(range) — usually far cheaper than testing every candidate one at a time, but not free.
• Prefer this technique whenever the answer range is large but a single feasibility check is fast — that combination is the strongest signal this pattern applies.

Practice Exercises

1. Split Array Largest Sum: Given an array of positive integers nums and an integer k, split nums into k non-empty contiguous subarrays so the largest sum among them is as small as possible. Return that minimized largest sum. Hint: binary search on the answer with low = max(nums) and high = sum(nums); the feasibility check greedily counts how many subarrays are needed to keep every subarray sum at or below a candidate value.
2. Aggressive Cows: Given the positions of n stalls along a line and an integer c (number of cows), place all c cows into stalls so the minimum distance between any two cows is as large as possible. Return that maximum possible minimum distance. Hint: sort the stall positions first, then binary search on the minimum distance; the feasibility check greedily places cows, always skipping ahead to the next stall at least the candidate distance away.
3. Minimum Days to Make Bouquets: Given bloomDay (the day each flower blooms) and integers m and k, you need m bouquets, each requiring k adjacent already-bloomed flowers. Find the minimum number of days to wait before all m bouquets can be made. Try bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1 — expected answer 3. Hint: binary search on the day, with feasibility counting how many bouquets can be assembled from consecutive already-bloomed flowers by that day.

Summary

• Binary search on the answer turns “find the optimal value satisfying a condition” problems into a search over candidate answers, using a monotonic feasibility check instead of a direct array comparison.
• It requires a provably valid [low, high] range and a feasible(candidate) predicate that is monotonic across that entire range.
• Time complexity is O(f(n) × log R), where f(n) is the cost of one feasibility check and R is the size of the answer range; space is O(1) extra beyond the input.
• Use the while low < high / high = mid template when searching for the smallest feasible value — mixing it with the low <= high exact-match template is the most common source of infinite loops.
• Always double-check that chosen bounds are themselves valid answers to search within; an invalid bound can silently break monotonicity and produce a wrong answer without crashing.
• Classic applications include minimizing the maximum load (Split Array Largest Sum), maximizing a minimum distance (Aggressive Cows), and minimizing a resource like speed, capacity, or time (Koko Eating Bananas, Ship Within Days, Minimum Days to Make Bouquets).