Binary Search on the Answer

In short: when "is this value good enough?" flips from no to yes exactly once as the value grows, you can binary search the answer itself, not just a sorted list. Pick a range you know contains the answer, write a yes/no feasibility check, prove in one sentence that it's monotone, then halve the range with the usual template. A range of a billion costs about 30 checks — the search is never the bottleneck, the check is.

Quarry splits every table into shards, and each shard holds at most c rows. A table with r rows therefore needs $\lceil r / c \rceil$ shards, and the cluster has room for a fixed budget of shards across all tables. Big shards are slow to move and rebalance, so the capacity tuner wants the smallest c that still fits every table into the budget.

There's no sorted list here to search, and there's no formula that gives c directly, because the ceilings get in the way. But look at the output. As c grows, the shard count never goes up. So the question "does capacity c fit in 6 shards?" reads no, no, no, …, yes, yes, yes as c increases. It flips exactly once. Anything that flips exactly once can be binary searched.

You've done this once already

In the binary search lesson, grid_side found the biggest square grid of album covers, and first_true found the first day a track crossed a million plays. Neither searched a list. Both searched a range of possible answers with a yes/no test. This lesson turns that trick into a method you can apply on purpose. It has four questions, and you should answer them in a comment before writing the loop:

1. What is the answer space? Pick lo and hi so that the answer is certainly inside. hi must be a value you know works. Here c = max(tables) puts every table in one shard, so if any capacity fits, that one does.
2. What is the test? A function fits(c) that says yes or no. This is often called the feasibility check, and it's usually a simple greedy or counting loop.
3. Is it monotone, and which way? No-then-yes means you want the first yes (a smallest capacity). Yes-then-no means you want the last yes (a largest gap, a biggest grid).
4. What does one test cost? The search makes about $\log_2 R$ tests over a range of size $R$, so the total is $O(\log R \times \text{test})$.

Watching the answer space shrink

Here are the capacities from 1 to 30 as cells. Each probe tests one capacity, and because the test is monotone, a single answer rules out a whole side:

Now run it on your own test. Change budget, or rewrite fits completely, and watch where the probes land:

Two templates, and the one bug that hangs

Almost every search on the answer is one of these two loops. Learn them as a pair:

The rounding is not a style choice. In last_true, rounding down with lo = 3, hi = 4 gives mid = 3, the test passes, lo = mid leaves lo at 3, and the loop never ends. Whichever side keeps mid, round mid away from it.

How many probes does a big range take? Fewer than you might think:

When the test is not monotone

Binary search trusts the test completely. After one "no" it never looks left of mid again. If the test can say yes, then no, then yes, the search can step straight over the real answer:

So before you binary search an answer, prove the test is monotone in one sentence. For shards: a bigger capacity never needs more shards for any table, so if c fits, c + 1 fits. For "place replicas at least d apart": if you can do it with gap d, the same placement works for any smaller gap. If you can't write that sentence, don't binary search.

Feasibility checks are usually greedy

Quarry places k replicas of a hot index on racks at the positions in racks, and it wants them as far apart as possible, to survive a local failure. Maximising the smallest gap directly is hard. Checking a proposed gap is easy: walk the racks in order and place a replica whenever you're at least d from the last one. Placing as early as possible never hurts, so if this greedy walk can't place k replicas, nothing can.

The largest gap that passes is a last-true search over d from 0 up to racks[-1] - racks[0]. That's the drill exercise.

Recognising the pattern

Search on the answer rarely announces itself. These phrasings are the usual signals:

• "the smallest X such that…" or "the largest X such that…", where X is a number: a capacity, a speed, a size, a time limit, a distance;
• "minimise the maximum…" or "maximise the minimum…". The replica problem above is one, and so is the smallest daily listening cap from the binary search lesson, where the goal was to make the busiest day as light as possible;
• a problem that is hard to optimise but easy to check. If you can't see how to compute the best c, but given a c you could quickly say whether it works, that's the signal.

The last one is the real test. Binary search on the answer turns an optimisation problem ("find the best") into a sequence of decision problems ("is this good enough?"), and decision problems are usually much easier to write correctly. You pay a factor of $\log R$ for the conversion, which is almost always a bargain.

❓ Cross-question — "Couldn't I just try every capacity from 1 upwards?" You could, and on the four small tables above it would take 15 checks instead of 4. But the answer space for a real cluster runs to millions of rows per shard. A linear scan pays one check per candidate, while binary search pays one check per halving. Over a range of a billion that's the difference between a billion checks and thirty.

The hi bound is where most bugs hide. It has to be a value that you know passes:

How much can one check cost?

The search makes about 30 probes over a range of a billion, so the budget for the whole search is really a budget for the check. Quarry's tuner has to answer within 200 ms, and 2³⁰ is just over a billion, so each of the 30 checks gets about 6 ms. A 20 ms check would take 600 ms in all. That's why feasibility checks are written as tight O(n) loops. An O(n log n) check or an O(n²) one multiplies straight into the total.

Answers that aren't whole numbers

The same halving works on real numbers, with one change: there's no "lo == hi" moment, so run a fixed number of rounds. Sixty halvings shrink any sensible range below floating-point precision. Say Quarry models its cache hit rate as size / (size + 40) and wants the smallest size giving 95% hits:

Interview problem: the k-th smallest latency gap

Sometimes the check is a count. "Is the answer at most d?" becomes "are there at least k things of size at most d?", and that flips once as d grows.

The k-th smallest gap. Quarry compares every pair of requests in a trace and looks at the difference in their latencies. Given latencies and k, return the k-th smallest of those differences, counting from 1. There are n·(n−1)/2 pairs, and listing them all is too slow.

Constraints: 2 ≤ n ≤ 10⁵, 0 ≤ latencies[i] ≤ 10⁶, 1 ≤ k ≤ n·(n−1)/2.

Examples:

• kth_gap([12, 40, 19, 33], 2) → 7. The gaps sorted are 7, 7, 14, 21, 21, 28.
• kth_gap([5, 5, 9], 1) → 0

Sort the latencies. Then "how many pairs have a gap of at most d?" is a single two-pointer sweep, and the smallest d for which that count reaches k is the answer, found with first_true. It costs O(n log n) for the sort plus O(n log R) for the search, where R is the largest gap. That's the boss exercise.

What it costs

Idioms & real-world patterns

• Write the monotonicity sentence first, in a comment, before any code.
• Pick hi so it is certainly feasible, and lo so it is either the smallest possible answer or certainly infeasible.
• Round mid away from the side that keeps it.
• Keep the check separate: fits(c) as its own function, tested alone.
• Where it shows up: capacity planning, choosing timeouts and batch sizes, finding the first bad build in a history, rate limits, and many "minimise the maximum" or "maximise the minimum" problems.

⚡ Advanced — bisect can search an answer space too

bisect_left accepts any sequence, and since Python 3.10 a key. A range is a lazy sequence, so you can hand it the whole answer space without building a list:

It is tidy, but it hides the four questions. Write the loop by hand until those questions are automatic.

Quick practice

🎯 Your turn

Build min_capacity(tables, budget) for Quarry's capacity tuner. tables lists each table's row count (each at least 1). A table with r rows needs $\lceil r / c \rceil$ shards at capacity c. Return the smallest whole-number c >= 1 whose total shard count fits in budget, or -1 if no capacity can (every table needs at least one shard). With no tables, return 1.

• min_capacity([30, 11, 23, 4], 6) → 15
• min_capacity([30, 11, 23, 4], 3) → -1

Hint: search c from 1 to max(tables) with the first-true template. The test is shards_needed(tables, c) <= budget.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅