Search the Answer
What is this?
A shop assistant is finding your shoe size without a measuring device. She does not inspect your foot and compute an answer. She hands you a size, asks "too tight?", and halves the range. Nothing is being searched in the usual sense; the candidate answers are the search space, and a yes/no test navigates them.
That is this chapter. You are given no sorted array at all. You invent one out of the possible answers.
Fun fact: Maximum Value at a Given Index in a Bounded Array is a binary search whose predicate is closed-form arithmetic rather than a loop. Once the peak value is fixed, the cheapest possible array descends by one on each side and then flattens out at 1, so the minimum total is two arithmetic series plus a flat remainder, computable in O(1). Each feasibility check needs no loop, so the solution is
O(log(maxSum)), and getting the series formula right matters more than the search.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
The idea: if the problem says "smallest / largest / minimum possible x such that…", then
xis your search space. Writefeasible(x), prove it flips exactly once, and binary-search the flip.
1. The three steps
Step 1: bound the space. Pick lo and hi that certainly bracket the answer. Sloppy bounds are the commonest source of wrong answers: lo must be a value that might be feasible, and hi one that certainly is. For Heaters, lo = 0 and hi = the largest possible coordinate distance.
Step 2: write the predicate. feasible(x) answers "can the goal be met with this value?" It is usually a greedy sweep in O(n), occasionally a formula in O(1).
Step 3: prove monotonicity. If a radius of 5 covers every house, so does 6. If a ship of capacity 20 delivers in time, so does 21. State the argument out loud. It is what makes the approach valid, and candidates often skip it.
lo, hi = 0, max_possible
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid # mid works, it might be the smallest that does
else:
lo = mid + 1 # mid fails, the answer is strictly larger
return lo
That is the template for "smallest x that works". For "largest x that works" (the bounded-array problem) flip it: mid = lo + (hi - lo + 1) // 2 rounds up, feasible means lo = mid, infeasible means hi = mid - 1.
2. When the predicate is a formula
For the bounded-array problem, fix the peak value v at index i. The cheapest array with that peak descends v−1, v−2, … outward until it hits 1, then stays flat. Each side is therefore an arithmetic series plus a flat tail:
Add both sides plus v itself and compare with the budget. No loop, no simulation. The feasibility check is O(1), so the whole solution is O(log(maxSum)).
3. A 30-second worked example (Heaters)
Houses at [1, 2, 3, 4], heaters at [1, 4]. What is the smallest radius covering every house?
Feasibility is monotonic in the obvious way: if radius r covers every house, r + 1 covers a superset of the same area. That one sentence is the justification the whole solution rests on.
4. Where you'll actually meet this
- Capacity and autoscaling. "What is the smallest cluster size that keeps p99 latency under target?" Feasibility is measured by a load test and is monotonic by assumption.
- Facility placement. Heaters is a coverage problem (cell towers, warehouses, charging stations) asking for the minimum service radius.
- Build and deploy tooling.
git bisectbinary-searches commits on the monotone predicate "is the bug present?". - Numerical root-finding. Bisection over a continuous range, with the same monotonicity requirement.
5. Problems in this chapter
Maximum Value at a Given Index in a Bounded Array
Maximise the value at a given index subject to a sum limit and adjacent values differing by at most one. Binary-search the peak; feasibility is two arithmetic series in O(1).
Pattern: search the answer, closed-form predicate. Target: O(log(maxSum)) time, O(1) space.
Heaters
Find the minimum heater radius covering all houses. The lesson's main solution sorts the heaters, binary-searches each house's nearest heater and takes the maximum distance. Binary search on the radius with a greedy coverage check is the general framing.
Pattern: search the answer, greedy predicate. Target: O((n + m) log m) time and O(m) space for the direct method; the radius search costs an extra log(range) factor.
6. Common pitfalls
- Not proving monotonicity. If
feasiblecan flip more than once, binary search returns an arbitrary point. This is the step that matters. - Bad bounds.
himust certainly be feasible andlomust be a legal candidate; otherwise the loop converges on a value that was never valid. - Mixing loop conventions. For the smallest feasible x,
while lo < hipairs withhi = midandlo = mid + 1. For the largest, it pairs with a round-up midpoint,lo = midandhi = mid - 1. Rounding down withlo = midloops forever oncehi = lo + 1. - Overflow in
(lo + hi) / 2. Uselo + (hi - lo) // 2, a habit worth keeping even in Python, since the interview language may not be Python. - Off-by-one in the arithmetic series. The peak itself must be counted once, not once per side.
- Forgetting the flat tail. When the descent reaches 1 before the array ends, the remaining cells each contribute 1, not 0.
- Missing the simpler solution. Heaters has a direct answer (nearest heater per house, take the max); binary search on the radius is instructive but not the only route, and saying so is a plus.
7. Key takeaways
- "Smallest/largest x such that…" means x is the search space. Recognising that phrasing is most of the battle.
- Feasibility is the design work, and it is usually a greedy sweep or a formula.
- Monotonicity is the licence. Prove it in one sentence before writing the loop.
- Bound the space carefully. Bad bounds produce plausible, wrong answers.
- Pick the loop template to match the question. Smallest x:
while lo < hi,hi = mid,lo = mid + 1, returnlo. Largest x: round the midpoint up,lo = mid,hi = mid - 1. - An O(1) predicate makes the whole thing logarithmic. Look for closed forms before reaching for simulation.
- Why interviewers love it: the problem statement contains no array and no mention of searching, so recognising the pattern at all is the signal.
Order: Maximum Value at a Given Index in a Bounded Array → Heaters.
The pattern is introduced in Coding Interview 101, for example Capacity To Ship Packages Within D Days and Koko Eating Bananas. Do those first; the two here assume you can already spot the monotonic predicate unaided.
Heaters
Core idea: Every house must be reached by some heater, and a single uniform radius covers all houses iff it covers the hardest-to-reach one. Each house's "hardness" is the distance to its nearest heater, and the answer is the largest of those nearest distances.
Problem, rephrased
Winter is coming, and a utility company must pick the one warming radius it will ship on every heater along a straight rural road. It is a single dial setting applied fleet-wide, so the smallest setting that leaves no home cold is worth real money. You're given two integer arrays: houses, where houses[i] is the position of a house on the line, and heaters, where heaters[j] is the position of a heater on the same line. Every heater gets the same radius r, and a house is warm if it sits within distance r of at least one heater (|house - heater| <= r), so a heater warms both its left and its right.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson