Binary Search on the Answer

"Binary search on the answer" is the pattern where you binary-search over the range of possible answers rather than an array — applicable whenever a candidate answer has a monotonic feasibility (if x works, everything larger/smaller works). It solves minimise-the-maximum and maximise-the-minimum problems that look nothing like search at first glance.

The core idea

Identify a value range [lo, hi] for the answer and a boolean feasibility check feasible(mid) that is monotonic. Binary-search the smallest (or largest) feasible value: if feasible(mid), move toward the optimum, else move away. Cost is O(log(range) × cost of feasible). The hard part is spotting the monotonicity and writing feasible() — often a greedy O(n) simulation.

Problem	Search over	feasible(x)	Time
Koko eating bananas	eating speed	finishes in ≤ h hours	O(n log(max))
Ship packages in D days	capacity	fits in ≤ D days	O(n log(sum))
Split array largest sum	max subarray sum	≤ m subarrays	O(n log(sum))
Minimise max distance	distance	achievable	O(n log(range))

Exam Tricks & Tips

• 🎯 "Minimise the maximum" / "maximise the minimum" / "smallest x such that..." → binary search on the answer.
• 🎯 The answer space must be monotonic: if x is feasible, all larger (or all smaller) x are too.
• 🎯 Write feasible(mid) as a greedy O(n) check; total is O(n log(range)).
• 🎯 Set lo/hi to the true min/max possible answer (e.g., max element to total sum).
• 🎯 It converts an optimisation into a decision problem you can binary-search.
• ❌ Common mistake: applying it when feasibility isn't monotonic — then binary search is invalid.

Expected pattern

Koko eating bananas, capacity to ship packages in D days, split array largest sum, minimum days to make bouquets, or "smallest divisor given a threshold". Interviewers expect you to spot monotonicity and code the feasibility check.

Quick recap

When the answer has a monotonic feasibility test, binary-search the answer range instead of an array. Write a greedy O(n) feasible(mid); total O(n log(range)). It cracks minimise-max / maximise-min optimisation problems.

Cover the answer, recall, then check. 11 cards on binary search on the answer.

Q1. When can you binary search on the answer?
A1. When candidate answers have a monotonic feasibility: if x works, all larger (or all smaller) x also work.

Q2. What replaces the array comparison?
A2. A boolean feasible(mid) check, usually a greedy O(n) simulation.

Q3. Overall complexity?
A3. O(log(range) × cost of feasible), typically O(n log(range)).

Q4. Phrases that signal this pattern?
A4. "Minimise the maximum", "maximise the minimum", "smallest/largest x such that...".

Q5. Koko Eating Bananas — what do you search over?
A5. The eating speed; feasible = can finish all piles within h hours.

Q6. How do you set lo and hi?
A6. To the smallest and largest possible answers (e.g., max single element to total sum).

Q7. Split Array Largest Sum — search variable and check?
A7. Search the maximum allowed subarray sum; feasible = array splits into ≤ m parts under that cap.

Q8. Why does this pattern work at all?
A8. Monotonic feasibility turns an optimisation into a decision problem amenable to binary search.

Q9. Ship Within D Days — search space?
A9. Ship capacity, from the max package weight to the total weight.

Q10. What breaks the technique?
A10. Non-monotonic feasibility — then a feasible mid gives no directional information.

Q11. Typical structure of feasible(mid)?
A11. A single O(n) greedy pass counting groups/time/steps and comparing against the constraint.

The most powerful use of binary search isn't searching an array at all — it's searching the space of possible answers. When a problem asks for the minimum/maximum value that satisfies a monotonic condition, you can binary-search the answer even with no sorted array in sight.

Core idea: if a predicate feasible(x) is monotonic — false, false, …, true, true (or the reverse) — then binary search finds the boundary value (the smallest feasible x, or largest) in O(log(range) × cost-of-check), without enumerating every candidate.

How it works

Beginner — the pattern

Define a boolean feasible(x) that is monotonic in x, then binary-search the answer range:

lo, hi = minPossible, maxPossible
while lo < hi:
    mid = lo + (hi - lo)//2
    if feasible(mid): hi = mid        # mid works; try smaller
    else: lo = mid + 1                # mid too small; go higher
return lo                             # smallest feasible answer

The array isn't searched — the answer axis is.

Intermediate — recognising monotonicity

The trick works when "if x works, every larger (or smaller) x also works". Examples:

• Koko eating bananas / ship packages in D days: a bigger speed/capacity is always feasible → find the smallest that fits the deadline.
• Split array into K subarrays minimising the largest sum: a larger allowed max is easier → find the smallest max.
• Minimum days / minimum capacity / smallest divisor problems all fit this mould.

Advanced — complexity and the check

Total time = O(log(hi − lo)) × O(check). The check (feasible) is usually an O(n) greedy simulation, so overall O(n log(range)) — dramatically better than O(range·n) brute force. The two design steps: (1) identify the monotonic predicate, (2) write an efficient feasibility check.

Worked example

Koko eats n piles; find the min speed to finish in H hours. feasible(speed) = "total hours at this speed ≤ H", computed by summing ceil(pile/speed) — O(n), and monotonic (faster speed → fewer hours). Binary-search speed in [1, max(pile)]: each mid runs the O(n) check, total O(n log(maxPile)). The boundary where feasible flips false→true is the answer.

When to use it

• "Minimise the maximum" / "maximise the minimum" optimisation problems.
• "Smallest/largest value such that a condition holds": minimum speed/capacity/divisor, minimum days, allocate books/pages, aggressive cows, painters partition.
• Whenever a candidate answer can be checked faster than searched for, and feasibility is monotonic.

Tricks & gotchas

• The predicate must be monotonic — verify the "if x works, x±1 also works" direction before applying.
• Set lo/hi to the true answer bounds (e.g. max element to total sum for partition problems).
• Return lo after the lo < hi / hi = mid loop for the smallest feasible answer.
• Mnemonic: "Can't find it? Guess it and check — binary-search the answer."

Key formulas

• Binary-search the answer space when a monotonic feasibility predicate exists.
• Total time O(n · log(range)): each of log(range) guesses runs an O(n) feasibility check.
• Predicate must be monotone: feasible for all x ≥ t (or ≤ t).
• Range = [min possible, max possible] of the answer.
• Classic uses: minimum capacity, Koko eating bananas, allocate minimum pages.

Usage: frame the problem as "smallest x for which feasible(x) is true", then binary search x.

Worked Example

Problem: Koko eats bananas from piles [3, 6, 7, 11]. At speed k bananas/hour she needs Σ ceil(pile / k) hours. Find the minimum integer speed k so she finishes within h = 8 hours.

Solution: As k increases, the hours needed only decrease — a monotonic predicate — so we can binary-search k over [1, max pile = 11]. feasible(k) = (hours(k) ≤ 8).

lo	hi	k=mid	hours(k) = Σ ceil(pile/k)	feasible?	move
1	11	6	1+1+2+2 = 6	yes	hi = 6
1	6	3	1+2+3+4 = 10	no	lo = 4
4	6	5	1+2+2+3 = 8	yes	hi = 5
4	5	4	1+2+2+3 = 8	yes	hi = 4

Loop ends with lo = hi = 4, the smallest feasible speed.

Each check is O(n) and there are O(log(max)) checks → O(n log(max)).

Answer: Minimum speed k = 4 bananas/hour.