Binary Search on Answer: The Pattern, the Template, and When It Fails

You get "cut N cables into at least K equal pieces, maximize the piece length" and there is no sorted array anywhere in sight. Binary search on the answer means you stop searching the input and start searching the space of possible answers instead: piece lengths 1 through the longest cable. For each candidate length you ask one yes/no question — can I get K pieces this long? — and because that answer flips at most once as the candidate grows, binary search finds the boundary in a few dozen checks.

Key Takeaways

• Recognize the pattern by the ask, not the data: "minimize the maximum", "maximize the minimum", "smallest X such that", "largest X such that". None of these require a sorted input.
• The pattern only works when the feasibility predicate is monotone: feasible(x) must read as an unbroken run of false then true (or true then false) across the answer space. One flip back and binary search returns garbage with full confidence.
• Total cost is O(check × log(range)). A linear greedy or counting check gives O(n log range), which is usually the intended answer when the DP alternative is quadratic.
• The decision version has to be strictly cheaper than the optimization version. If "can we reach total reward R" is as hard as the original problem, binary search buys you nothing; weighted job scheduling is the classic false positive.
• Most bugs live in the shrink step, not the check. Record every feasible mid in a best variable and you cannot lose the answer to an off-by-one.

The pattern: search answers, not arrays

Asked at Bloomberg — Find maximum cable length by cutting You are handed N cables with integer lengths and need to produce at least K pieces, all cut to the same integer length L. The interviewer wants the largest L that still yields K pieces, and 0 if even L = 1 falls short. A follow-up asks how you would handle fractional lengths at 1e-3 precision.

Nothing in this problem is sorted. What it has instead is an answer space (L runs from 1 to the longest cable) and a cheap question you can ask about any candidate: how many pieces of length L do the cables yield? That count is sum(c // L) over all cables, computed in one pass.

Now the property that makes the whole pattern legal. Take cables = [8, 5] and k = 4, the instance we will trace end to end. As L grows, the piece count can only shrink or stay flat, so the predicate pieces(L) >= 4 reads as a run of trues followed by a run of falses:

L:          1  2  3  4  5  6  7  8
pieces(L): 13  6  3  3  2  1  1  1
feasible:   T  T  F  F  F  F  F  F

You are looking for the last true. That is a binary search boundary problem, and the search never touches the cables again; it walks candidate lengths.

Here is the canonical maximize template. I recommend the explicit best variable over the lo-converges-to-answer style: it is immune to the off-by-one that costs candidates five minutes of whiteboard debugging.

def max_piece_length(cables, k):
    lo, hi = 1, max(cables)
    best = 0                            # answer if nothing is feasible
    while lo <= hi:
        mid = (lo + hi) // 2            # candidate piece length
        pieces = sum(c // mid for c in cables)
        if pieces >= k:                 # mid works — try to do better
            best = mid
            lo = mid + 1
        else:                           # mid too ambitious
            hi = mid - 1
    return best

Trace it on the same cables = [8, 5], k = 4. Range is 1..8. mid = 4: pieces = 2 + 1 = 3, infeasible, hi = 3. mid = 2: pieces = 4 + 2 = 6, feasible, best = 2, lo = 3. mid = 3: pieces = 2 + 1 = 3, infeasible, hi = 2. Loop ends, return 2. That matches the table above: the last true sits at L = 2.

Complexity is O(n log maxLen): the check is O(n) and the search runs at most log2(maxLen) iterations, about 30 for lengths up to 10^9. Space is O(1).

Two classic mistakes on this exact problem. Starting lo at 0 puts a division by zero one unlucky midpoint away. And the best = 0 initialization is not decoration: it is the "return 0 if impossible" clause from the problem statement. People who prefer the lo-converges style have to bolt that clause on separately, and it is the part that gets forgotten until the impossible test case fails.

"Minimize the maximum" is the loudest tell

Asked at Microsoft — Solve load balancing and perfect pairs The first half of this two-part question gives you m tasks in a fixed order and n identical servers. Each server must take one contiguous block of tasks, the blocks must cover the sequence in order, and a server's load is the sum of its block. Minimize the largest load any server carries.

This is the split-array-largest-sum shape, and the phrase "minimize the maximum" should trigger the pattern before you finish reading the constraints. Flip the question around: instead of asking "what is the smallest achievable max load?", ask "if I cap every server at load cap, can n servers cover all the tasks?"

That decision version has a greedy answer. Sweep the tasks left to right, packing the current server until the next task would push it past cap, then open a new server:

def servers_needed(times, cap):
    used, load = 1, 0
    for t in times:
        if t > cap:                 # a single task exceeds the cap
            return float('inf')
        if load + t > cap:
            used += 1
            load = t
        else:
            load += t
    return used

The greedy is correct here because tasks are consumed in order and stretching any server as far as the cap allows can never force more servers later. That one-sentence argument is worth saying out loud; expect the follow-up to be why the check is right, not just what it computes. If greedy correctness arguments feel shaky, the failure cases in our greedy algorithm guide are the right warm-up.

servers_needed(times, cap) is non-increasing in cap, so servers_needed(cap) <= n is monotone: false, false, ..., true, true. Binary search cap over [max(times), sum(times)] — the tightest possible cap is the largest single task, the loosest is one server doing everything — and take the first true. That is O(m log(sum)).

The mistake that kills this problem is proposing the DP first. There is a legitimate O(m^2 n) interval DP, and at interview-scale m the quadratic term is dead on arrival. Getting stuck optimizing that DP is the standard way to burn the clock without ever reaching the reframe. Lead with the decision version.

The check is where the interview actually happens

Asked at Amazon — Find minimum days to deliver all orders You run N delivery centers and a list of orders, each addressed to some city 1..N. A center spends 1 day of its capacity on an order for its own city and 2 days on an order for anywhere else, and every center can put in one day of work per calendar day. Find the minimum number of days to clear every order.

The binary search shell for this is ten lines and every prepared candidate can produce it. What separates people is the feasibility check, because it is not a one-liner here.

Fix a candidate day count D. Each center has a budget of D order-days. Its own city's orders cost 1 day each, so it clears up to D of them locally; spending cheap local capacity first is safe, because a local order costs 1 at home and 2 anywhere else, so home is never the wrong place for it. Whatever budget remains can absorb reassigned orders, and here is the detail the problem statement plants for you: a reassigned order occupies two days on the one center it lands on. Those two days cannot be split across centers, so a center with left leftover days absorbs left // 2 reassigned orders and an odd final day simply goes to waste. The check: after every center clears its local orders, count the orders still unserved, and test whether sum((D - min(local_c, D)) // 2) across centers covers them.

The tempting shortcut, pooling raw leftover days and asking whether the pool covers the remainder at 2 days apiece, is the classic wrong version of this check. Three centers, D = 1, two orders for city 1: center 1 clears one order, centers 2 and 3 each have one spare day, and the pooled test sees 2 spare days and declares D = 1 feasible. But the leftover order needs two days on a single center, and no center has two. The per-center floor is not pedantry; it is the check.

Monotonicity is easy to argue and worth arguing explicitly: any schedule that clears everything in D days is also a valid schedule for D + 1 days, so feasibility never flips back off. State that sentence in the interview. It is the load-bearing claim, and a plausible-looking predicate that silently is not monotone is the classic way this pattern produces confidently wrong answers.

My honest advice for this family: budget two thirds of your time for the check and its correctness argument, one third for everything else. The search loop is a commodity. The check is the problem.

When the answer space is the data's own values

Asked at Meta — Find kth smallest in sorted matrix Given an n×n matrix whose rows and columns are each sorted in nondecreasing order, return the k-th smallest element. The interviewer explicitly wants two approaches compared: a min-heap over row heads versus binary search over the value range, with complexities and edge cases for both.

The previous three answer spaces were scalars you constructed: a piece length, a load cap, a day count. Here the answer space is the matrix's own value range, everything between matrix[0][0] and matrix[n-1][n-1], and most of the candidates you probe are not elements of the matrix at all.

The predicate: for a candidate value v, is count(v) >= k, where count(v) is how many matrix entries are ≤ v? Counting takes O(n) with a staircase walk: start at the bottom-left corner; if the current entry is ≤ v, everything above it in that column also is, so add the column count and step right; otherwise step up. The count is nondecreasing in v, so the predicate is monotone, and the smallest v with count(v) >= k is the answer.

One subtlety that interviewers probe: the search converges to a value that actually exists in the matrix, even though most midpoints do not. For an integer matrix searched over integer values, the proof is two lines: if the smallest v satisfying the predicate were absent from the matrix, then v − 1 would have the same count and also satisfy it, contradicting minimality. That argument is the difference between knowing the trick and understanding it.

The comparison the Meta question asks for, honestly filled in:

Neither dominates. For k = 5 in a 1000×1000 matrix, the heap's cost is dominated by heapifying the 1,000 row heads; the five pops after that are noise. Call it roughly a thousand operations against the value search's n log range, which is 30,000 or more, and the heap wins by over an order of magnitude. At k = 900,000 the k log n term is the whole story, the heap does millions of operations, and the flat value search wins comfortably. If the heap half of that table is the shaky one for you, our heap guide covers when to reach for one and when not to.

Real-valued answers and the precision trap

Asked at Atlassian — Minimize max L1 radius with k centers in 1D You get n integers on a number line, possibly negative and with repeats, and an integer k. Place k centers anywhere on the real line so that the largest distance from any point to its nearest center is as small as possible, and return that distance. The stated bar is beating the O(nk) DP.

Centers can sit anywhere on the real line, so the answer is not obviously an integer, and the reflex is to start typing while hi - lo > 1e-9. Hold that thought.

The check first: sort the points once, then for a candidate radius r, sweep left to right greedily. The leftmost uncovered point p forces a center somewhere, and placing it at p + r covers as far right as any legal choice can, so skip every point within p + 2r and repeat. Feasible if the sweep uses at most k centers. That is O(n) per check after an O(n log n) sort.

Now the senior move: notice you never need floating point at all. Any group of points spanning [a, b] is covered optimally by a center at the midpoint with radius (b − a) / 2, so the optimal radius is always half of some integer gap. Binary search the diameter d = 2r over integers 0 to max(A) − min(A), run the same sweep with windows of width d, and return d / 2 at the end. Exact answer, integer arithmetic, no epsilon anywhere. This is the same discretization instinct the Minimize L1 distance with k cluster centers variant is testing, and it turns an analysis question into a clean integer search.

When the answer genuinely is continuous — the Bloomberg cable follow-up about cutting to 1e-3 precision is exactly this — do not loop on hi - lo > eps. With large magnitudes, hi - lo can get stuck above your epsilon forever because the floats have no representable value in between. Run a fixed iteration count instead:

for _ in range(100):        # halves the interval 100 times
    mid = (lo + hi) / 2
    if feasible(mid):
        lo = mid            # maximize: keep the feasible side
    else:
        hi = mid

Forty iterations shrink any starting interval by a factor of 2^40 ≈ 10^12, which buries 1e-3 precision with room to spare. A hundred costs nothing and removes the entire class of termination bugs.

When binary search on the answer does not apply

Asked at Airbnb — Maximize profit from non-overlapping jobs Up to 200,000 jobs, each with a start time, end time, and reward. Pick a set of pairwise non-overlapping jobs maximizing total reward, return that maximum, and reconstruct one optimal set. The expected bar is O(N log N).

This problem says "maximize", its intended solution contains a binary search, and it is not binary search on the answer. It is the most useful negative example in the bank.

Try to force the pattern and watch it fail: the predicate would be "can we reach total reward ≥ R?" That predicate is monotone, sure, but checking it is exactly as hard as solving the original problem. There is no cheap greedy that decides it. The pattern's real precondition is not monotonicity alone; it is that the decision version is strictly easier than the optimization version. Cable cutting: optimization looks hard, decision is one division per cable. Job scheduling: decision and optimization are the same DP wearing different hats.

What the O(N log N) solution actually does is sort jobs by end time, run a DP where dp[i] is the best reward using the first i jobs, and use binary search to find the latest job ending at or before job i's start. That binary search walks sorted indices: it is a lookup subroutine inside a DP, the same primitive doing a completely different job. The nearly identical Maximize reward by scheduling jobs adds a correctness-proof requirement on top, and neither is answerable by searching an answer space.

The pre-flight check, as a decision procedure:

Two more disqualifiers worth naming. Predicates about hitting a target exactly ("can we make exactly k groups") are frequently non-monotone, feasible at k and k+2 but not k+1, and binary search over them silently returns nonsense. And when the answer space itself is small (say, 1 to 50), just scan it linearly; a log factor on 50 candidates is not worth a single boundary bug.

Practice these on PracHub

Start with the template drills:

• Find maximum cable length by cutting (Bloomberg): the cleanest template drill, with a one-line counting check, the maximize variant, and the floating-point follow-up.
• Find kth smallest in sorted matrix (Meta): value-space search plus the heap trade-off discussion; drills the "does the answer actually exist" argument.

Then the ones where the check is the problem:

• Solve load balancing and perfect pairs (Microsoft): minimize-the-maximum with a greedy check whose correctness you should be able to argue in one sentence.
• Find minimum days to deliver all orders (Amazon): the check is a genuine capacity-allocation subproblem with the per-center floor trap from above; good rehearsal for arguing monotonicity explicitly.
• Minimize max L1 radius with k centers in 1D (Atlassian): continuous-looking answer that discretizes to an integer search; the precision discussion starts here.

Finish with the negative example:

• Maximize profit from non-overlapping jobs (Airbnb): prove to yourself why the pattern does not apply before writing the DP.

More of the family lives under coding questions, the ML-flavored variants under interview questions, and the neighboring pattern guides under resources.