Binary Search on the Answer

Some problems ask you to minimize or maximize a number (a speed, a capacity, a time, a largest sum) that has to meet a threshold. The input doesn't need to be sorted. What's sorted is the answers: if a value works, every bigger (or smaller) value works too. So you guess a value, ask a yes/no function whether it's feasible, and binary search the guesses.

The idea#

Write a function feasible(x) that returns True or False for a guess x. If it's monotone (it flips from false to true, or true to false, only once), binary search applies:

Minimize: feasible is false, false, …, true, true. Find the first true. On success, record the guess and go left.
Maximize: feasible is true, true, …, false, false. Find the last true. On success, record the guess and go right.

The search makes $O(\log(\text{range}))$ guesses. Each check usually walks the input once, $O(n)$ , so the total is $O(n \log(\text{range}))$ .

The hard part is rarely the search. It's the two things around it:

Bounds. lo is the smallest answer that could possibly work and hi the largest you would ever need.
The check. Usually a greedy pass: "with this capacity, how many days do you need?"

How to spot it#

These cues suggest searching the answer space.

"Minimum speed / capacity / time such that…", "maximize the minimum", "minimize the maximum".
Constraints like n ≤ 10^5 with values up to 10^9: the value range is huge but its log is about 30.
Checking one candidate is easy, but choosing the best directly is hard.
A DP over choices looks tempting, but the pieces must be contiguous. Then a greedy check per guess is often enough.

Template#

Here is a generic "minimize" search. The answer is the first feasible value.

feasible(x): one greedy pass; True if guess x works
lo = smallest answer that could work
hi = largest answer you would ever need   # feasible(hi) is True
ans = hi
while lo <= hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        ans = mid          # works: record it, then try smaller
        hi = mid - 1
    else:
        lo = mid + 1       # too small: everything below fails too
return ans

To maximize, swap the two moves: on success record the guess and set lo = mid + 1; on failure set hi = mid - 1.

Counting values ≤ a guess, and the ghost guess#

The same search also answers "Kth smallest" questions, with one trap. These problems search by value: count how many values are ≤ x, then find the first x with count ≥ k.

Why not stop when the count equals k? The guess might be a ghost: a value that isn't in the input at all. In a 3 × 3 multiplication table the products are {1, 2, 3, 4, 6, 9}, and 5 is missing.

Row	Values ≤ 5	Count
1	1, 2, 3	3
2	2, 4	2
3	3	1
Total		6

For k = 6 the guess 5 already has count 6, yet the 6th smallest value is 4. Only the first value with count ≥ k is guaranteed to exist, so keep searching left after a hit.

Closest instead of feasible#

A last variation drops the yes/no check altogether. Some problems have no yes/no answer: you want the value whose result is closest to a target. Let the pointers cross, then compare the results at r (the floor) and l (the ceiling) and keep the closer one. This is the sandwich from Binary Search Boundaries.

Pitfalls#

The search is easy to write. The mistakes hide in the setup around it.

Loose or wrong bounds. If hi can be infeasible, the template returns a wrong answer; if lo is too high, you miss the true minimum.
Going the wrong way. Minimize: success goes left. Maximize: success goes right.
Stopping at count == k. The guess may be a ghost value; take the first value with count ≥ k.
Float ceilings. math.ceil(a / b) works for small numbers, but -(-a // b) is exact for any size.
Missing the impossible case. If no guess in range can ever work, return the failure value before you search.
Counting runs wrongly. When the check needs adjacent items, reset the run counter on an item that fails.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Koko Eating Bananas

Guess a speed. It's feasible when the hours sum(ceil(p / speed)) fit in h. Search speeds from 1 to max(piles) and minimize.

Hint: Find the Smallest Divisor Given a Threshold

A divisor d is feasible when sum(ceil(x / d)) <= threshold. Use the exact integer ceiling -(-x // d). Search 1..max(nums); for [1, 2, 5, 9] with threshold 6 the answer is 5.

Hint: Maximum Candies Allocated to K Children

This one maximizes. A pile size c is feasible when sum(pile // c) >= k. On success go right. If even size 1 fails, the answer is 0.

Hint: Capacity To Ship Packages Within D Days

Fix the capacity and load packages greedily in order, starting a new day when the next one would overflow. Feasible when that takes at most days. The smallest capacity that could work is the heaviest package.

Hint: Minimum Number of Days to Make m Bouquets

If m * k > len(bloomDay), no number of days is enough, so return -1 before searching. For a guessed day, count runs of adjacent bloomed flowers, and reset the run on a flower that hasn't bloomed.

Hint: Minimum Time to Repair Cars

A mechanic with rank r repairs k cars in r · k² minutes. Invert it: in t minutes a mechanic fixes isqrt(t // r) cars. The upper bound is the best mechanic doing every car alone, min(ranks) * cars².

Hint: Split Array Largest Sum

It looks like DP, because you choose where to cut. But the pieces are contiguous. Fix the largest allowed sum, walk the array greedily, and start a new piece whenever the sum would overflow. Feasible when that needs at most k pieces.

Hint: Maximum Running Time of N Computers

Running n computers for T minutes needs n · T battery-minutes. A battery with b ≥ T sits in one computer and its surplus is wasted; a smaller one can be swapped around and fully used. So each battery contributes min(b, T), and the upper bound is sum(batteries) // n.

Hint: Kth Smallest Number in Multiplication Table

Row i holds i, 2i, …, n·i, so it has min(n, x // i) values ≤ x. Find the first x with count ≥ k; stopping at count == k can return a ghost. The same idea fits Kth Smallest Element in a Sorted Matrix.

Hint: Sum of Mutated Array Closest to Target

There is no yes/no check. Let the pointers cross, then compare the sums at r and l. Prefer the smaller value on a tie.

Hint: Valid Perfect Square

Search the answer x in 1..num. If x * x is too big, go left; too small, go right. Stop when it hits num exactly or the range is empty.

Key takeaways#

If "x works" implies "anything bigger works" (or smaller), binary search x.
Separate the search from a feasible(x) function; the check is usually a greedy pass.
Minimize: record and go left. Maximize: record and go right.
Get the bounds from the problem's extremes, and handle the impossible case first.
For "Kth value" searches, take the first value with count ≥ k; a guess can be a ghost.

Core idea#

The input need not be sorted. The answers are sorted: if a value works, every bigger (or smaller) value works too. Guess a value, test it with a yes/no feasible(x), and binary search the guesses.

Key points#

feasible(x) must be monotone.
Minimize: false, ..., true. Find the first true. On success, record and go left.
Maximize: true, ..., false. Find the last true. On success, record and go right.
Cost is $O(n \log(\text{range}))$ : about 30 guesses for a range of $10^9$ , one $O(n)$ check each.
The hard parts are the bounds and the check, not the search.
lo is the smallest answer that could work. hi is the largest you would ever need.
The check is usually a greedy pass: "with this capacity, how many days do you need?"
Spot it: "minimum speed / capacity / time such that", "maximize the minimum", "minimize the maximum".

Common checks#

Problem	Feasible when
Split Array Largest Sum, Ship Packages	greedy contiguous pieces ≤ `k`
Smallest Divisor	`sum(ceil(x / d)) <= threshold`
Repair Cars	`sum(isqrt(t // r)) >= cars`
N Computers running `T`	`sum(min(b, T)) >= n * T`
Kth in Multiplication Table	`sum(min(n, x // i)) >= k`

Template#

lo = smallest answer that could work
hi = largest answer you would ever need   # feasible(hi) is True
ans = hi
while lo <= hi:
    mid = (lo + hi) // 2
    if feasible(mid):      # one greedy pass
        ans = mid          # works: record, try smaller
        hi = mid - 1
    else:
        lo = mid + 1       # everything below fails too
return ans

To maximize, swap the moves: on success record and set lo = mid + 1.

Pitfalls#

Loose bounds. An infeasible hi or a too-high lo gives a wrong answer.
Stopping at count == k. The guess can be a ghost value that is not in the input. Take the first value with count ≥ k.
Float ceilings. Use -(-a // b), which is exact for any size.
The impossible case. In the bouquets problem, if m * k > len(bloomDay), return -1 before you search.

Say it in an interview#

"If x works, anything bigger works, so binary search x with a feasibility check."
"In Split Array Largest Sum the pieces are contiguous, so a greedy check replaces DP."