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). The whole problem becomes O(log(max)) with no iteration at all, which is why 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 one-line idea: if the problem says "smallest / largest / minimum possible x such that…", then x is your search space. Write feasible(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 — this is the part that makes the whole approach valid, and it is the part candidates skip.

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

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:

side of length L with peak neighbour value v-1:
  if v - 1 >= L:  sum = (v-1 + v-L) * L / 2          full descent
  else:           sum = (v-1)*v/2 + (L - v + 1)      descent to 1, then 1s

Add both sides plus v itself and compare with the budget. No loop, no simulation — and the feasibility check is O(1), which is what makes the whole solution O(log(max)).

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?

radius 0 → house 2 uncovered (nearest heater is 1 away)    ✗
radius 1 → houses 1,2 covered by heater 1
            houses 3,4 covered by heater 4                  ✓
                                        smallest radius = 1

binary search over [0, 3]:
  mid = 1 → feasible → hi = 1
  lo = 0, hi = 1 → mid = 0 → not feasible → lo = 1
  lo == hi == 1                                     answer = 1

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 measured by a load test, monotonic by assumption.
• Rate limiting. The largest request rate that keeps error rates acceptable.
• Facility placement. Heaters is a real coverage problem — cell towers, warehouses, charging stations — asking for the minimum service radius.
• Build and deploy tooling. git bisect binary-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. Binary-search the radius with a greedy coverage check — or sort both arrays and take the maximum nearest-heater distance directly.
Pattern: search the answer, greedy predicate. Target: O((n + m) log(range)), or O(n log n) via the direct method.

6. Common pitfalls 🚫

• Not proving monotonicity. If feasible can flip more than once, binary search returns an arbitrary point. This is the step that matters.
• Bad bounds. hi must certainly be feasible and lo must be a legal candidate; otherwise the loop converges on a value that was never valid.
• Mixing loop conventions. while lo < hi pairs with hi = mid and lo = mid + 1. Combining it with hi = mid - 1 loops forever or skips the answer.
• Overflow in (lo + hi) / 2. Use lo + (hi - lo) // 2 — a habit worth keeping even in Python, since interviews are polyglot.
• 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 sorted-two-pointer answer; binary search is instructive but not the only route, and saying so is a plus.

7. Key takeaways

1. "Smallest/largest x such that…" means x is the search space. Recognising that phrasing is most of the battle.
2. Feasibility is the design work, and it is usually a greedy sweep or a formula.
3. Monotonicity is the licence. Prove it in one sentence before writing the loop.
4. Bound the space carefully. Bad bounds produce plausible, wrong answers.
5. One loop template, always. while lo < hi, hi = mid, lo = mid + 1, return lo.
6. An O(1) predicate makes the whole thing logarithmic — look for closed forms before reaching for simulation.
7. 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 two problems that introduce this pattern — Capacity To Ship Packages Within D Days and Kth Missing Positive Number — are in Coding Interview 101. Do those first; the two here assume you can already spot the monotonic predicate unaided.