Search the Answer

What is this?

This is the clever leap that surprises everyone: instead of searching through your data, you search through the possible answers. Picture asking "could I finish in 5 hours?" — if no, you clearly need more time, and if yes, you wonder whether even less would do. Because "is this much enough?" only ever flips from no to yes once as you allow more, you can guess-and-halve your way to the smallest amount that works, even when the answer is a speed, a capacity, or an amount of time rather than a spot in a list.

💡 Fun fact: "Search the answer" is exactly how engineers size real systems — to find the smallest server fleet that keeps a website fast, you binary-search the count by repeatedly load-testing a guess, instead of trying every possible number one by one.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: When a problem asks for the smallest (or largest) value that satisfies some condition, you do not search an array at all — you binary-search the range of possible answers. If "does answer x work?" flips from no to yes exactly once as x grows, that monotonic boundary is exactly what binary search finds, turning a huge answer space into O(log range) feasibility checks.

The pattern

This is the most powerful idea in the chapter: binary search on the answer. Instead of looking for a position, you guess a candidate answer and ask a yes/no feasibility question — and the cost of that single guess is usually a quick O(n) pass.

It works only when feasibility is monotonic: once some value is good enough, every larger (or every smaller) value is too. That gives a clean threshold to home in on. The recipe is always the same. First, identify the answer and its bounds — a lo that is obviously too small and a hi that obviously works. Second, write feasible(x): given candidate x, can the task be done? Third, binary-search for the boundary, biasing toward the smallest x that is feasible (or the largest, depending on the ask).

The skill is recognising the shape: "minimum capacity," "minimum speed," "minimum time," "maximum size that fits" all hide a monotonic feasibility test behind them.

The problems

Koko Eating Bananas — find the slowest eating speed that clears all piles within h hours. Faster is always feasible, so it is monotonic. Check feasibility of a min speed: for candidate speed k, sum the hours needed and test against h; binary-search the smallest k that fits.

Capacity To Ship Packages Within D Days — find the smallest ship capacity that delivers everything in D days. Check feasibility of a min capacity: greedily pack days under capacity c, count days used, and search for the smallest c needing at most D days. lo is the largest single package, hi is the total.

Minimum Time to Complete Trips — find the least total time for buses to finish a quota of trips. Count trips at a time budget: at candidate time t, each bus does t / time[i] trips; sum them and search for the smallest t meeting the quota.

Arranging Coins — find how many full rows a staircase of n coins can form. The answer is the largest k with k(k+1)/2 ≤ n — a triangular number threshold you binary-search directly.

Key takeaways

• Binary-search the answer, not an array. When you want the smallest/largest value that works, the answer space is your search range.
• Feasibility must be monotonic. "Good" values must form one contiguous side; otherwise binary search cannot bracket them.
• Each guess costs one O(n) check. Total cost is O(n log range) — usually a massive win over brute force.
• Set bounds deliberately. A lo that is too small and a hi that always works keep the loop correct and the boundary inside.
• Why this chapter matters: "search the answer" reframes optimization as search, and it is one of the most common and highest-leverage interview patterns.