vault

Binary Search on Answer

21 min read

Binary Search on Answer

Binary search on the answer is a meta-pattern: when the answer you’re looking for lies in some integer (or real) interval and the property “is x a valid answer?” is monotone in x — i.e., once a value works, every value above it works (or once it works, every value below it works) — you can binary-search for the boundary. The input itself need not be sorted; the answer space is what’s monotone. The algorithm becomes: write a feasible(x) -> bool predicate, then bisect over the integer range [lo, hi] to find the smallest (or largest) x for which feasible(x) holds. Each call to feasible does some real algorithmic work — usually a linear simulation, sometimes a greedy check — and the binary search wraps it in O(log(hi − lo)) iterations. Total complexity: typically O(n × log(value range)). The pattern unlocks a huge family of “minimum X such that Y” interview problems that look hopeless from the outside.

1. Intuition — Setting the Right Faucet Pressure

Imagine a stadium with a faucet that fills cups for the audience. You can dial the faucet’s pressure from 0 to 100. At low pressure, the cups don’t fill in time — fans get thirsty. At high pressure, they overflow — but at any pressure above some threshold, the cups do fill in time.

You want the minimum pressure at which everyone gets a full cup. You don’t have a formula for it, but you can test any specific pressure by running an experiment (“turn the faucet to 60, time how long the cups take, see if everyone is served”). The experiment is monotone: if pressure 60 works, pressure 61 also works; if pressure 60 fails, pressure 59 also fails.

Naively, you’d test pressures 0, 1, 2, … until one works — O(n) experiments. With binary search you test the middle (50). If 50 works, the answer is in [0, 50]; if not, in [51, 100]. Halve the range each step: O(log n) experiments to find the boundary. With n = 10⁹ pressure settings, that’s 30 experiments instead of a billion.

The crucial mental shift: you’re not binary-searching the input (the list of fans, or the cup capacities), you’re binary-searching the answer space — the candidate values for the unknown you’re trying to determine. The input gets passed wholesale into the feasible predicate, which simulates “what if the answer were x?” and returns yes/no.

This is sometimes called parametric search in the algorithms-theory literature — see Megiddo’s 1983 paper on “Applying parallel computation algorithms in the design of serial algorithms.” The technique applies to any optimization problem whose decision-version is easier than the optimization-version and where the decision-version’s answer is monotone in the parameter being optimized.

2. Tiny Worked Example — Capacity to Ship Packages in D Days

You have packages with weights w = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. You must ship them in 5 days, in order (no reordering — package 3 ships before package 4). What’s the minimum ship capacity?

Observation 1 — answer bounds. The capacity must be at least max(w) = 10 (otherwise package 10 can’t fit on any day). It need be at most sum(w) = 55 (one day, all packages, definitely works). So the answer is in [10, 55].

Observation 2 — monotonicity. If capacity c works (we can ship in ≤ 5 days), then any c' > c also works (we have more slack). The set of valid capacities is [answer, ∞) — a contiguous suffix.

Observation 3 — the predicate. feasible(c) := "can we ship everything in ≤ 5 days using capacity c?" Implementation: greedily pack packages onto the current day until the next one would exceed c, then start a new day. Count the days; return days ≤ 5.

The binary search trace:

Iterationlohimidfeasible(mid)?Action
1105532days = 2 ≤ 5 ✓answer ≤ 32: hi = 32
2103221days = 3 ≤ 5 ✓answer ≤ 21: hi = 21
3102115days = 5 ≤ 5 ✓answer ≤ 15: hi = 15
4101512days = 6 > 5 ✗answer > 12: lo = 13
5131514days = 5 ≤ 5 ✓answer ≤ 14: hi = 14
6131413days = 6 > 5 ✗answer > 13: lo = 14
Exit1414answer = 14

Six iterations to find the answer in a 46-wide range — log₂ 46 ≈ 5.5, so 6 is exactly what we expect. Each feasible call did 10 weight-additions, so total work was ~60 simple operations. A naive scan would have been 46 × 10 = 460. The win grows with the range: for weights up to 10⁶ summing to 10¹¹, naive is hopeless and binary search is ~37 × n.

3. The Pattern Recognition Signal

This is the pattern-recognition section of this note — recognizing when to reach for binary-search-on-answer is the meta-skill, and it converts otherwise-intractable problems to ~20-line solutions.

Reach for binary search on answer when any of these phrases appear:

  1. “Find the minimum X such that …” or “smallest X for which …” — classic monotone “minimum threshold” framing.
  2. “Find the maximum X such that …” — the dual.
  3. “What is the minimum/maximum capacity / speed / size / value / time …” — a parametric optimization where you can simulate any specific candidate.
  4. “Split into K parts so that the largest part is minimized” — the minimax structure (LC 410, “split array largest sum”).
  5. “Distribute / place K things subject to constraints” — often reducible to “is X feasible?” via a greedy check.
  6. “Allocate items to workers/days/groups so that the makespan / load / cost is at most/least X” — the predicate is “can we do it in time/cost X?”
  7. The naive answer would require enumerating an exponentially large space of configurations, but checking a single candidate answer is polynomial.
  8. The problem hands you a clear answer range — explicit bounds like “1 ≤ answer ≤ 10⁹” or implicit ones like “the answer is at most max(arr)” — combined with no obvious O(n) closed-form formula.

The inverse signals — when binary search on answer is the wrong tool:

  • The “is X feasible?” predicate isn’t monotone in X. (E.g., “is there a subset of weights summing to exactly X” — non-monotone; subset-sum is NP-hard.)
  • The answer space is discrete, small, and irregular — direct enumeration is fine.
  • The problem asks you to count configurations rather than find an extremal one. Binary search finds the boundary; counting needs other techniques.
  • The predicate evaluation itself is exponentially expensive — then the wrapper doesn’t help.

The monotonicity test to apply mentally before committing: “if x works, does x + 1 also work? if x fails, does x − 1 also fail?” If yes to both, the answer space is monotone and binary search applies. If you’re unsure, prove it. Mistaking a non-monotone predicate for monotone is the #1 way binary-search-on-answer goes silently wrong.

4. Pseudocode

The standard form uses Binary Search’s template 3 (lower-bound / leftmost-true) — find the smallest x for which feasible(x) is true. (See the Binary Search note’s §5 for the three template variants and why this template specifically uses half-open [lo, hi) semantics.)

4.1 Minimum X Such That feasible(X)

binary_search_min(lo, hi, feasible):
    # Invariant: answer is in [lo, hi]; feasible(hi) must be true.
    while lo < hi:
        mid := lo + (hi - lo) / 2
        if feasible(mid):
            hi := mid                  # mid might be the answer
        else:
            lo := mid + 1              # mid is too small
    return lo

4.2 Maximum X Such That feasible(X)

binary_search_max(lo, hi, feasible):
    # Invariant: answer is in [lo, hi]; feasible(lo) must be true.
    while lo < hi:
        mid := lo + (hi - lo + 1) / 2  # ROUND UP — see pitfall 8.2
        if feasible(mid):
            lo := mid
        else:
            hi := mid - 1
    return lo

The asymmetry — rounding up in the max version — is necessary to avoid an infinite loop when lo + 1 == hi and feasible(lo) is true.

4.3 Setting Up the Range — Bound Choice Cookbook

Picking lo and hi correctly is half the problem:

  • Capacity to ship: lo = max(weights) (must hold the heaviest package); hi = sum(weights) (one day suffices).
  • Koko eating bananas (rate): lo = 1 (positive integer rate); hi = max(piles) (can eat any single pile in one hour).
  • Split array largest sum: lo = max(nums); hi = sum(nums).
  • Minimum time / minimum size: lo = 1; hi = some safe upper bound like sum or n × max.

The rule of thumb: lo is the smallest value for which the predicate could conceivably be true; hi is a value for which it definitely is. If you accidentally start with feasible(hi) = false, the algorithm returns garbage — usually lo == hi == hi_initial.

5. Python Implementation

5.1 LC 1011 — Capacity to Ship Packages Within D Days

def ship_within_days(weights: list[int], days: int) -> int:
    def feasible(capacity: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > capacity:
                d += 1
                load = 0
            load += w
        return d <= days
 
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The feasible predicate is a greedy linear simulation: pack packages onto the current day until adding the next one would overflow, then start a new day. The greedy is optimal here because packages must ship in order — there’s no benefit to leaving room on day k for a future package; you might as well pack densely.

5.2 LC 875 — Koko Eating Bananas

Koko has piles of bananas. She eats at rate k bananas/hour: each hour she picks a pile and eats up to k (if the pile is smaller, she eats it all and moves on). Find the minimum integer rate k so she finishes within H hours.

import math
 
def min_eating_speed(piles: list[int], h: int) -> int:
    def feasible(k: int) -> bool:
        return sum(math.ceil(p / k) for p in piles) <= h
 
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The math.ceil(p / k) is the time to finish a single pile of size p at rate k. Sum across all piles, compare to budget. The monotonicity is obvious in retrospect: faster eating ⇒ fewer hours.

5.3 LC 410 — Split Array Largest Sum

Split a non-negative integer array nums into k non-empty contiguous subarrays. Minimize the largest subarray-sum.

def split_array(nums: list[int], k: int) -> int:
    def feasible(max_sum: int) -> bool:
        groups, cur = 1, 0
        for x in nums:
            if cur + x > max_sum:
                groups += 1
                cur = x
            else:
                cur += x
        return groups <= k
 
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

This is structurally identical to ship-within-days — only the variable names change. Recognizing that “split into k parts to minimize the max” and “minimum capacity to ship in d days” are the same problem under a relabeling is the kind of transferable insight that interviews reward.

5.4 LC 1552 — Magnetic Force Between Two Balls

Place m balls in baskets at integer positions pos[] (sorted) such that the minimum pairwise distance between balls is maximized. Note the “max-min” structure — opposite of the prior problems.

def max_distance(position: list[int], m: int) -> int:
    position.sort()
 
    def feasible(d: int) -> bool:
        # Can we place m balls so that consecutive balls are >= d apart?
        count, last = 1, position[0]
        for p in position[1:]:
            if p - last >= d:
                count += 1
                last = p
                if count >= m:
                    return True
        return count >= m
 
    lo, hi = 1, position[-1] - position[0]
    # Maximum d such that feasible(d) — use the max-X template
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2          # round up
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

The greedy in feasible: walk left-to-right, place a ball every time you have at least d distance from the last placed ball. This greedy is optimal — placing earlier never hurts, since any later valid placement remains valid after an earlier-placed ball. The monotonicity is “smaller required distance ⇒ easier to place ⇒ more balls fit.”

5.5 LC 1283 — Find the Smallest Divisor Given a Threshold

Find the smallest divisor d such that sum(ceil(num / d) for num in nums) <= threshold.

import math
 
def smallest_divisor(nums: list[int], threshold: int) -> int:
    def feasible(d: int) -> bool:
        return sum(math.ceil(n / d) for n in nums) <= threshold
 
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Same pattern again, fundamentally interchangeable with Koko bananas — different cover story, identical math.

6. Complexity

Time: O(P × log(hi − lo)) where P is the cost of one feasible call and (hi − lo) is the answer range.

For the canonical problems above, P = O(n) (a linear simulation over the input array) and log(hi − lo) ≤ log(sum(nums)) ≤ log(n × max(nums)). For n = 10⁵ and max = 10⁹, log(n × max) ≈ 47, so the total is ~5 × 10⁶ operations — fast.

Space: O(1) beyond the input — the predicate runs in place, and the binary search uses two scalars.

Why this beats brute force. The brute-force approach would enumerate every candidate answer x in [lo, hi] and call feasible(x), giving O((hi − lo) × P) — for the same problem above, that’s 5.5 × 10¹¹ operations, infeasible. Binary search shrinks the leading factor from (hi − lo) to log(hi − lo) — typically a 10⁵–10⁹ × speedup depending on the answer range.

The complexity savings show their full power when the answer range is exponential in the input size: for a value range of 10¹⁸ (say, sum of large weights), brute force is impossible, binary search is ~60 × P. The logarithm doesn’t care how astronomical the range is.

A subtle point: the predicate must run in polynomial time for binary-search-on-answer to be useful. If the predicate itself is NP-hard (e.g., “is there a partition of nums into k subsets each with sum ≤ x?” for general subsets, not contiguous), binary searching it yields a polynomial wrapper around an exponential routine — no improvement. The pattern works precisely because the decision version of the problem is dramatically easier than the optimization version. Parametric search formalized this observation.

7. Variants and Sub-patterns

7.1 Binary Search on Real-Valued Answers

When the answer is a real number (e.g., “minimum cost X such that…”, LC 644 “max average subarray II”), binary-search the real interval. Replace the integer-update rules with:

while hi - lo > epsilon:
    mid = (lo + hi) / 2.0
    if feasible(mid): hi = mid
    else:             lo = mid
return lo

Pick epsilon based on the required precision (often 10⁻⁵ or 10⁻⁶ in competitive problems). The number of iterations is log₂((hi₀ − lo₀) / epsilon) ≈ 50 for typical inputs.

7.2 Binary Search on Two Predicates (Find a Range)

When you want all values for which the predicate is true (the property holds in a contiguous interval), binary-search both endpoints. E.g., “find the range of valid speeds” — binary-search the smallest valid speed and the smallest invalid speed.

7.3 Binary Search on a Function’s Argmax / Argmin (Ternary Search Cousin)

If the value (not the predicate) is unimodal in x (single peak/valley), use Ternary Search instead of binary search — the predicate isn’t monotone but the value is bitonic.

7.4 Aggressive Cows / Magnetic Force

Same problem under different cover stories: place k entities in n slots to maximize the minimum gap. SPOJ’s “Aggressive Cows” predates LC 1552 (Magnetic Force) by over a decade. The greedy-place-from-left predicate is identical.

7.5 Median of Two Sorted Arrays (LC 4)

A non-obvious binary-search-on-answer: binary-search the partition position in the smaller array such that the combined left half contains the smaller (m + n + 1) / 2 elements. The predicate is “is the partition valid?” (i.e., does left_max ≤ right_min across both sides?). The answer space is the partition position in [0, len(smaller)]. O(log(min(m, n))) total. This is the gold-standard hard binary-search interview problem.

sqrt(n) for an integer n: binary-search the largest x with x² ≤ n. The predicate x² ≤ n is monotone in x. O(log n).

7.7 Allocate Books / Painters

A classic SPOJ/InterviewBit problem: assign n books with given page counts to m students (each student gets a contiguous range) so that the maximum pages assigned to any student is minimized. Same structure as split-array-largest-sum.

7.8 Time-Based Predicates

Some problems ask “minimum time to…” where the predicate is “given t time, can we…?” Examples: minimum time to repair cars, minimum time to make m bouquets (LC 1482), minimum time to complete trips (LC 2187). All identical structure — set up lo, hi time bounds, predicate is a counting/feasibility check.

8. Pitfalls

8.1 Non-Monotone Predicate

The single biggest failure mode. Before writing the binary search, prove monotonicity: explicitly verify “if feasible(x) then feasible(x + 1)” (or the dual). If the proof feels shaky, it probably is. Common false assumptions: “if I can do it in time T, I can do it in time T − 1 with a more clever schedule” — usually wrong; cleverness doesn’t add monotonicity.

A worked counterexample: subset-sum-to-exactly-X is not monotone — feasible at X = 7 doesn’t imply feasible at X = 8 (different subsets, no inclusion relation). Don’t binary search this.

8.2 Infinite Loop in the Max-X Template

When lo + 1 == hi and feasible(lo) is true, computing mid = (lo + hi) // 2 = lo and then setting lo = mid = lo — no progress, infinite loop. The fix in §4.2 is mid = lo + (hi - lo + 1) // 2 (round up), which gives mid = hi in this case, and either feasible(hi) is true (set lo = hi, exit) or false (set hi = mid - 1 = lo, exit).

The off-by-one correction is the most common bug in max-X binary searches; min-X binary searches don’t suffer because rounding down already advances lo correctly. See Binary Search §11 for the deeper “off-by-one trifecta.”

8.3 Wrong Initial Bounds

If feasible(hi) is false, the algorithm returns hi (or lo, depending on template), which is wrong. Always sanity-check that feasible(hi) == True and feasible(lo - 1) == False (i.e., the answer is strictly within [lo, hi]). For the canonical problems, hi = sum(weights) is large enough because shipping everything in one day always works.

8.4 Confusing the Input Range with the Answer Range

You’re not binary-searching the indices of the input; you’re binary-searching the value the answer can take. New practitioners sometimes set lo, hi = 0, n - 1 (input indices) instead of lo, hi = max(weights), sum(weights) (value range). The mid then has no semantic meaning in the predicate. Always think: “what does a candidate answer look like, and what range can it span?“

8.5 Predicate That Modifies the Input

The predicate is called many times (~30 times for typical ranges). If it sorts or otherwise mutates the input, sort once outside the binary search and pass the sorted view in — don’t re-sort inside feasible. Otherwise total cost is O(n log n × log(range)) instead of O(n × log(range)).

8.6 Greedy in the Predicate Is Not Always Correct

The predicate often uses a greedy simulation, and the greedy needs its own correctness argument. For “ship in D days,” the greedy “pack onto current day until full” is provably optimal (because order is fixed; no benefit to packing less densely). For “schedule jobs on m machines to minimize makespan” with arbitrary order, a greedy assignment is NOT optimal — that’s a different problem (NP-hard in general, requires LPT heuristic for approximation). Always verify the greedy.

8.7 Integer Overflow When hi = sum(arr)

For arrays of 10⁵ integers each up to 10⁹, sum can reach 10¹⁴ — fits in 64-bit, overflows 32-bit. Python is fine; in C++/Java use long long/long. Also use the mid = lo + (hi - lo) // 2 form to avoid lo + hi overflow even at intermediate steps.

8.8 Returning the Wrong Variable After the Loop

After the standard min-X loop, lo == hi and that common value is the answer. After the max-X loop, same. But if you exit via break partway through (e.g., found exact match), be deliberate about which variable you return. The cleanest discipline: never break inside binary-search-on-answer — always let the loop run to lo == hi. The rate of binary-search bugs caused by early breaks is high.

9. Diagram — Mapping the Predicate Truth Pattern

flowchart LR
    subgraph "Answer space (monotone)"
        F0["x=lo: ✗"] --> F1["x=lo+1: ✗"] --> F2["x=lo+2: ✗"] --> T0["x=ans: ✓"] --> T1["x=ans+1: ✓"] --> T2["x=hi: ✓"]
    end
    note["Binary-search the boundary between ✗ and ✓"]

What this diagram shows. The answer space [lo, hi] arranged left-to-right with the predicate’s truth value annotated on each value. Because the predicate is monotone — false on a prefix [lo, ans − 1], true on a suffix [ans, hi] — there is a single boundary point ans at which the predicate flips from false to true. Binary search finds this boundary in O(log(hi − lo)) probes by halving the candidate window each step. The crucial visual is the contiguous run of ✗ followed by a contiguous run of ✓ — that contiguity is the property that makes binary search applicable. If the truth pattern were ✗✓✗✓✗, no amount of bisection would find a meaningful answer; you’d be in the wrong problem class.

The dual (max-X) flips the picture: the predicate is true on [lo, ans] and false on [ans + 1, hi]. Same binary search, opposite update rule.

10. Common Interview Problems

#ProblemPredicate Shape
LC 1011Capacity to Ship Packages Within D DaysGreedy pack ≤ D days
LC 875Koko Eating BananasSum of ceiling divisions ≤ H
LC 410Split Array Largest SumGreedy split ≤ K parts
LC 1283Find Smallest Divisor Given ThresholdSum of ceiling divisions ≤ T
LC 1482Minimum Days to Make m BouquetsCount consecutive bloomed runs ≥ m
LC 1552Magnetic Force Between Two BallsGreedy place ≥ m balls (max-X)
LC 1760Minimum Limit of Balls in a BagSum of (s-1) // limit operations ≤ k
LC 2187Minimum Time to Complete TripsSum of time / each ≥ totalTrips
LC 2226Maximum Candies Allocated to k ChildrenSum of pile // candies ≥ k (max-X)
LC 2616Minimize the Maximum Difference of PairsGreedy pair adjacent in sorted order
LC 1898Maximum Number of Removable CharactersSubsequence-check predicate
LC 2064Minimized Maximum Products in a StoreDistribute n items to m stores
LC 4Median of Two Sorted ArraysPartition validity
LC 644Maximum Average Subarray IIReal-valued binary search
LC 774Minimize Max Distance to Gas StationReal-valued; place k gas stations
LC 668Kth Smallest in Multiplication TableCount cells ≤ x
LC 719Find K-th Smallest Pair DistanceCount pairs with distance ≤ x
LC 786K-th Smallest Prime FractionCount fractions ≤ x
LC 878Nth Magical NumberCount multiples ≤ x
LC 1300Sum of Mutated Array Closest to TargetSum after capping ≤ target
LC 1539Kth Missing Positive NumberCount missing ≤ x
LC 1870Minimum Speed to Arrive on TimeSum of ceiling / speed ≤ hours
LC 2389Longest Subsequence With Limited SumSort + binary search prefix sums
LC 287Find the Duplicate NumberCount elements ≤ mid (Floyd alternative)
SPOJ AGGRCOWAggressive CowsSame as LC 1552
SPOJ EKOWood Cutting ProblemCut at height H, total wood ≥ M
SPOJ PRATACooking Pratask cooks at speeds; t time enough?

11. Open Questions

  • What is the formal characterization of “decision-version is polynomial, optimization-version is binary-search-friendly”? Megiddo’s parametric search formalizes part of this; the broader characterization is open.
  • When should we use binary search on answer vs. a direct DP? Some problems admit both (e.g., Koko bananas could be solved by computing the answer formulaically; binary search is just simpler to write).
  • How does binary-search-on-answer interact with floating-point precision in real-valued problems? The “epsilon” choice is finicky and often determined empirically rather than analytically.

12. See Also

Graph View

Backlinks