Binary search on the answer

What this chapter covers

Binary search, from the searching tier, found a value in a sorted array by halving the search interval. This chapter applies the same halving to something that isn't an array at all — the space of possible answers to an optimization problem. Many "find the smallest (or largest) value such that some condition holds" problems have no visible search structure, yet they hide a monotone one: if a candidate answer works, every larger candidate works too (or every smaller one), so the answers are implicitly sorted by feasibility — a run of "no"s, a threshold, then a run of "yes"es. That's exactly what binary search needs. The move is to turn the hard optimization question ("what's the minimum?") into an easy decision question ("does this specific value work?"), and binary-search the decision. This chapter builds it on the painter's-partition problem — split an array into k parts to minimize the largest part's sum — and shows it asking 20 feasibility checks where scanning every candidate would ask 228,000.

A bit of history

Binary search itself is ancient in spirit and was formalized for computers in the 1940s and 50s (its first bug-free published implementation, Knuth noted, came surprisingly late — the boundary conditions are famously tricky). "Binary search on the answer" isn't a separate discovery so much as a recognition — the realization that binary search's only real requirement is a monotone predicate, not a physical sorted array. The same idea appears across numerical analysis as the bisection method for finding roots of continuous functions (if f is continuous and changes sign across an interval, binary-search the interval for the zero), which dates to the 19th century and earlier. In algorithm design and competitive programming it became a named, taught pattern in the 2000s, prized because it converts a large class of intimidating optimization problems into a trivial decision plus a loop. Its deeper lesson — that "optimize" often reduces to "decide, repeatedly" — echoes a central theme of complexity theory, where the relationship between optimization and decision problems is foundational (an NP optimization problem and its yes/no decision version are polynomially equivalent).

The intuition

Take the problem: split an array like [7, 2, 5, 10, 8] into k = 2 contiguous parts so that the largest part-sum is as small as possible. Optimizing this directly is awkward — where do the cut points go? But flip it into a decision: "can we split into at most 2 parts, each summing to at most L?" That question is easy to answer greedily — walk the array accumulating a running sum, and whenever adding the next element would exceed L, start a new part; count the parts and check if it's ≤ k. And here's the crucial property: this decision is monotone in L. If a limit L works, then any larger limit works too (more room per part means no more parts needed); if L is too small, so is everything below it. So as L increases from small to large, the answer to "does L work?" goes false, false, …, false, true, true, … — a single threshold. The smallest L that works is exactly the minimized largest-part sum we're after.

That threshold is what binary search finds. The answer must lie between max(nums) — no part can be smaller than the biggest single element — and sum(nums) — one part holding everything. Binary-search that range: test the midpoint L with the greedy check; if it works, the answer is L or smaller, so move the upper bound down to L; if it doesn't, the answer is larger, so move the lower bound up past L. Each check is O(n), and there are only O(log(range)) of them, so the whole thing is O(n log(sum)) — a handful of cheap decisions instead of trying every possible L. The pattern generalizes to any problem you can phrase as "smallest/largest X with a monotone yes/no property," and recognizing that shape — that an optimization is secretly a threshold search — is the whole skill.

Complexity: how it scales

Binary search on the answer costs O(log(range) × cost-of-one-check). For the split problem, the range is sum(nums) − max(nums) and each greedy check is O(n), giving O(n log(sum)). Compare the alternatives: scanning every candidate limit is O(range × n) — potentially enormous — and the exact dynamic program is O(n² k). The face-off measures the number of feasibility checks against a linear scan of the candidate space, as the answer range grows:

The linear-scan line climbs in step with the answer range — check every candidate — while the binary-search line is nearly flat, growing as its logarithm. When the answer space spans about two million values, the linear scan makes roughly 228,000 feasibility checks; binary search makes 20 — an eleven-thousand-fold difference, and the ratio keeps growing because one side is linear in the range and the other logarithmic. This is binary search's defining payoff, now applied to answers rather than array elements: each check halves the remaining possibilities, so doubling the answer space adds just one more check. The technique's value is that it makes the size of the answer space almost irrelevant — a range of a billion costs only ~30 checks — which is why it's the tool for problems where the answer could be any value in a huge numeric range.

What it's good at, what it isn't

Binary search on the answer is the right tool for optimization problems of the form "minimize/maximize X subject to a monotone feasibility condition," especially when X ranges over a large numeric space. The classics: "minimize the maximum" and "maximize the minimum" problems (split-array, painter's/book-allocation partition, placing k routers to minimize the largest gap), capacity and rate planning (smallest ship capacity to deliver in D days, minimum eating speed to finish in H hours, minimum server count to handle load), scheduling deadlines, and numeric root-finding and equation solving (the bisection method). It pairs naturally with a greedy or simulation feasibility check — the decision question is usually far easier than the optimization — and it turns problems that look like they need heavy DP or search into a short loop.

Where it doesn't apply is when the feasibility predicate isn't monotone — if some larger X fails where a smaller X succeeded, the answer space isn't sorted and binary search converges on nonsense; you must verify monotonicity first. It's also unnecessary when the answer space is tiny (just scan it) or when a direct formula or greedy gives the answer outright. And the feasibility check must be efficient — if deciding "does X work?" is itself expensive, O(log range) of them may not be a win. Finally, it finds a threshold value, not necessarily the full solution structure (which cut points, which assignment) — you often need a second pass to reconstruct the actual partition once you know the optimal limit. Its niche is precise: a monotone predicate over a large-but-searchable answer space with a cheap decision procedure.

The data, or the inputs

The face-off counts feasibility checks for the split-array problem — binary search against a linear scan of every candidate limit — as the answer range grows into the millions. Correctness is checked on a thousand random arrays: the binary-search answer must equal both the exact O(n²k) dynamic program and the linear scan, the feasibility predicate is verified to be genuinely monotone (once true as the limit grows, it never goes false again), and the integer-square-root example is checked against Python's math.isqrt on thousands of large numbers. The animation binary-searches the answer space [10, 32] for splitting [7, 2, 5, 10, 8] into 2 parts, testing each midpoint's feasibility and narrowing to the threshold.

Build it, one function at a time

The feasibility check — the easy monotone decision question, answered greedily:

def can_split(nums, k, limit):
    """The DECISION question: can `nums` be cut into at most k contiguous parts, each with sum ≤
    limit? Greedily extend the current part until adding the next element would exceed `limit`, then
    start a new part. Count the parts. O(n). This is monotone in `limit`: a larger limit can only
    make splitting EASIER (fewer parts needed), which is exactly what lets us binary-search on it."""
    parts, current = 1, 0
    for x in nums:
        if x > limit:
            return False                          # one element alone exceeds the limit — impossible
        if current + x > limit:
            parts += 1                            # close this part, start a new one with x
            current = x
        else:
            current += x
    return parts <= k

Binary-searching the answer space for the smallest feasible limit:

def min_largest_sum(nums, k):
    """Minimize the largest part-sum when splitting `nums` into k contiguous parts, by binary
    searching the ANSWER. The answer lies between max(nums) (no part can be smaller than the biggest
    single element) and sum(nums) (one part holds everything). Binary-search that range for the
    smallest limit the greedy check accepts. O(n · log(sum)) — a handful of O(n) checks, not a scan
    of every candidate. Returns the minimized largest-part sum."""
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(nums, k, mid):
            hi = mid                              # feasible → try to do even better (smaller)
        else:
            lo = mid + 1                          # infeasible → need a bigger limit
    return lo                                     # lo == hi == the smallest feasible limit

The same idea in miniature — integer square root as a monotone-predicate search:

def integer_sqrt(x):
    """A second, tiny example of the same idea: the integer square root of x is the largest v with
    v*v ≤ x — a monotone predicate (v*v ≤ x is true up to a threshold, false after), so binary-
    search v in [0, x]. O(log x), no floating point, exact."""
    lo, hi, ans = 0, x, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid                             # feasible → record it, look for a larger v
            lo = mid + 1
        else:
            hi = mid - 1                          # too big → look smaller
    return ans

Watch it work

Here's binary search on the answer space for splitting [7, 2, 5, 10, 8] into 2 parts to minimize the largest part. The cells are candidate limits from 10 (the biggest single element — no part can be smaller) to 32 (the total — one part holds everything). Unlike ordinary binary search, there's no data in these cells to compare against; instead, each tested midpoint is asked a question: "can we split into ≤ 2 parts each summing to at most this limit?" A green cell means yes (feasible), red means no. Watch the search narrow: it tests the middle, and because feasibility is monotone — every limit above the answer is green, every one below is red — a yes moves the search left (try smaller) and a no moves it right (need bigger). In a handful of feasibility checks it converges on 18: the smallest limit that admits a 2-way split ([7,2,5] sums to 14, [10,8] sums to 18). No part exceeds 18, and no smaller limit is possible:

The complete code

The from-scratch tab is the feasibility check, the binary search on the answer, and the integer-square-root example; the library tab is the exact O(n²k) dynamic program (the correctness reference) and the linear scan (the O(range) contrast). Flip between them — the binary search and the linear scan use the identical feasibility predicate, and the only difference is that one halves the search space each step and the other walks it one at a time.

"""Binary search on the answer — apply binary search not to a sorted array of data, but to the
space of possible ANSWERS to an optimization problem. Many "find the minimum/maximum value such
that..." problems have no obvious search structure, yet hide one: if a candidate answer works,
every larger (or smaller) candidate works too. That MONOTONICITY means the space of answers is
sorted by feasibility — infeasible values, then a threshold, then feasible values — and you can
binary-search for the threshold, even though there's no array to look at.

The trick is to turn the optimization ("find the smallest X such that P holds") into a sequence of
DECISION questions ("does P hold for this specific X?"). Each decision is usually easy — a greedy
check or a simulation. Binary search asks O(log(range)) of them instead of trying every candidate.
The example: split an array into k contiguous parts to MINIMIZE the largest part's sum (the
"painter's partition" / load-balancing problem). Directly optimizing is awkward; but "can we split
into ≤ k parts each summing at most L?" is a trivial greedy check, and it's monotone in L — so we
binary-search L for the smallest feasible value.
"""


# region: feasible
def can_split(nums, k, limit):
    """The DECISION question: can `nums` be cut into at most k contiguous parts, each with sum ≤
    limit? Greedily extend the current part until adding the next element would exceed `limit`, then
    start a new part. Count the parts. O(n). This is monotone in `limit`: a larger limit can only
    make splitting EASIER (fewer parts needed), which is exactly what lets us binary-search on it."""
    parts, current = 1, 0
    for x in nums:
        if x > limit:
            return False                          # one element alone exceeds the limit — impossible
        if current + x > limit:
            parts += 1                            # close this part, start a new one with x
            current = x
        else:
            current += x
    return parts <= k
# endregion


# region: binary_answer
def min_largest_sum(nums, k):
    """Minimize the largest part-sum when splitting `nums` into k contiguous parts, by binary
    searching the ANSWER. The answer lies between max(nums) (no part can be smaller than the biggest
    single element) and sum(nums) (one part holds everything). Binary-search that range for the
    smallest limit the greedy check accepts. O(n · log(sum)) — a handful of O(n) checks, not a scan
    of every candidate. Returns the minimized largest-part sum."""
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(nums, k, mid):
            hi = mid                              # feasible → try to do even better (smaller)
        else:
            lo = mid + 1                          # infeasible → need a bigger limit
    return lo                                     # lo == hi == the smallest feasible limit
# endregion


# region: isqrt
def integer_sqrt(x):
    """A second, tiny example of the same idea: the integer square root of x is the largest v with
    v*v ≤ x — a monotone predicate (v*v ≤ x is true up to a threshold, false after), so binary-
    search v in [0, x]. O(log x), no floating point, exact."""
    lo, hi, ans = 0, x, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid                             # feasible → record it, look for a larger v
            lo = mid + 1
        else:
            hi = mid - 1                          # too big → look smaller
    return ans
# endregion

"""The reference and the contrast. Two ways to solve the split-array problem without binary search:

- `dp_min_largest_sum` is the classic dynamic program — dp[i][j] = the minimized largest sum when
  splitting the first i elements into j parts. It's exact and it's the correctness reference, but
  it's O(n^2 · k), much heavier than the binary-search-on-answer O(n · log(sum)).
- `linear_scan_answer` finds the same threshold by trying EVERY candidate limit from low to high and
  returning the first feasible one. It uses the identical greedy check as binary search, just with a
  linear scan instead of a logarithmic one — the contrast that shows what binary search buys.

Both use the same feasibility predicate; the difference is only how many candidates each tests.
"""
import impl


# region: dp
def dp_min_largest_sum(nums, k):
    """The O(n^2 · k) dynamic program: dp[i][j] = min over the last split point p of max(dp[p][j-1],
    sum(nums[p:i])). Exact, and independent of the binary-search approach, so it's the reference the
    binary-search answer is checked against."""
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    INF = float("inf")
    dp = [[INF] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            for p in range(j - 1, i):             # last part is nums[p:i]
                dp[i][j] = min(dp[i][j], max(dp[p][j - 1], prefix[i] - prefix[p]))
    return dp[n][k]
# endregion


# region: linear
def linear_scan_answer(nums, k):
    """Find the threshold by trying every candidate limit from max(nums) up — the first that passes
    the greedy check is the answer. Same predicate as binary search, O(range) checks instead of
    O(log range). Returns (answer, checks_made)."""
    checks = 0
    for limit in range(max(nums), sum(nums) + 1):
        checks += 1
        if impl.can_split(nums, k, limit):
            return limit, checks
    return sum(nums), checks
# endregion

Scratch vs library

Binary search on the answer is the paradigms tier's most mind-expanding trick because it repurposes a familiar algorithm for an unfamiliar target: binary search's only real requirement is a monotone predicate, and once you see that, a sorted array is just one instance of it — the space of answers to an optimization problem is another. The reframe it teaches — "optimize" becomes "decide, repeatedly" — is broadly powerful, and it's the same decomposition that connects optimization and decision problems throughout complexity theory. The face-off's eleven-thousand-fold gap is the ordinary binary-search win (halving beats scanning) applied to a space you didn't know was searchable. It also composes beautifully with the other paradigms: the feasibility check is usually a greedy algorithm or a simulation, so binary-search-on-answer is often "binary search wrapped around greedy" — two techniques from this book combining into a third. There's no library function because it's a technique, and the skill it builds — recognizing the monotone answer-space hiding in a problem — is exactly the kind of pattern-sight that separates knowing algorithms from designing them.

Where you'll actually meet it

Binary search on the answer shows up wherever a capacity, rate, or threshold must be optimized. Capacity planning uses it — smallest ship, truck, or server capacity to meet a deadline or load; minimum bandwidth to clear a queue in time. Scheduling and manufacturing use "minimize the maximum" formulations (balance work across machines, minimize the latest completion). Numerical software uses the bisection method to solve equations and find roots where no closed form exists. Databases and systems tune parameters (buffer sizes, timeouts) by binary-searching a performance threshold. Competitive programming and technical interviews feature it constantly, precisely because the reframe from optimization to decision is a reusable insight. Machine learning uses it to calibrate thresholds and find hyperparameter boundaries. Rate limiters, load balancers, and resource allocators use it to size resources to a monotone demand curve. Anywhere the question is "what's the minimum resource that suffices?" — and more resource can't hurt — this technique is the efficient answer.

Takeaways

Binary search on the answer solves "find the smallest/largest X such that P(X)" by exploiting that P is monotone in X: the answers are implicitly sorted by feasibility, so you binary-search the threshold, turning an optimization into O(log range) easy yes/no feasibility checks. It made the split-array problem cost 20 checks where scanning every candidate cost 228,000, and it makes the size of the answer space nearly irrelevant. The requirements are a monotone predicate (prove it) and a cheap decision procedure (often a greedy check), and the common bugs are boundary conditions, not the core idea. The reframe — optimization is repeated decision — is the transferable lesson.

That completes the algorithm-design paradigms: divide and conquer, greedy, dynamic programming (with knapsack and sequence alignment), backtracking, two pointers, and binary search on the answer — the reusable strategies that generate algorithms, made explicit after appearing implicitly throughout the book. The final tier returns to concrete data structures, but advanced and often probabilistic ones — Bloom filters, skip lists, LRU caches, k-d trees, and reservoir sampling — structures that trade exactness or worst-case guarantees for dramatic gains in space or simplicity, and that power real systems at scale.