09Binary Search — On an Answer You Never Stored

01You can check it. You were asked to choose it.

How many machines do we rent so the nightly job finishes by six in the morning?

Nobody in the room answers that. Hand the same room a number instead — forty — and it turns competent in a second. Rent forty, start the job at ten at night, look at the clock in the morning. The job finished at 05:12, so forty machines are enough. That cost one night, and it settled nothing at all about thirty-nine.

The room could not choose a number. The room could check one.

Three more questions from the same month, and the same split runs straight through all of them. How high can we push the rate limit before p99 latency crosses 200 ms? Nobody at the table knows, so ask instead whether 3,000 requests a second holds p99 under 200 ms, and a twenty-minute load test says yes or no. Which of the last 800 commits broke the integration test? Nobody knows that either, so ask whether commit 400 on its own passes, and one build answers you in four minutes. How large a packet gets through this network path without being dropped somewhere in the middle? Nobody knows, so send one of 1,400 bytes and watch for it on the far side.

Look at what changed between the two versions of each question, because it is one word and it is not a small one. The question you were handed carries a superlative — how many, how high, which one, how large — and a superlative is a claim about every candidate at once. The question you can actually answer carries a specific number, and it asks about that number and nothing else. Forty machines, three thousand requests a second, commit 400, fourteen hundred bytes — each of those four is one experiment with a yes at one end and a no at the other, and you already know how to run it. Checking is bounded work. Choosing is not, and being excellent at the first has never once handed anybody the second.

That is the shape, and it is worth saying plainly before anything is done about it. Four rooms, four unrelated stacks — a rented fleet, a latency budget, a git history, a network path — and not one of the four can name its own answer. Every one of the four can settle a guess, cheaply, with a machine, on the first attempt. The distance between those two abilities is not a hole in what you know about fleets or packets, so no amount of thinking harder about packets closes it. It is a mismatch between the question you were asked and the instrument you happen to be holding. You own a checker, and you were asked for a chooser.

02The note this course wrote on page 6

This course already told you that gap can be closed, and you read the sentence three pages ago. Page 6 was busy with something else entirely. It was prising verification apart from search, and it wanted a cost question that could wear a yes-or-no face. So it bolted a threshold onto one, and then, in a single aside on its way elsewhere, it handed you this whole move: “Bolt a threshold on and the mismatch disappears… And the threshold gives the real number back whenever you want it, because binary search walks the answer down one yes-or-no question at a time. Twenty such questions pin any cost under a million (2²⁰ = 1,048,576).”

That is a promissory note, written in passing, and page 6 kept walking. Look at what it promises. You were left holding a checker when you were asked for a chooser, and page 6 answers that the checker was the chooser the whole time. Twenty answers name one cost out of page 6’s 1,048,576. Not twenty thousand. Not a sweep. Twenty. So the shortfall you were just handed is not a shortfall in your tools at all. It is a shortfall in what you were doing with the one tool you already owned.

Every word of that note is true, and not one word of it is a licence. Watch what the walking down actually does. It takes one answer about one guess, and on the strength of it throws away everything lying to one side. Page 6 deleted half of its million that way, and it never once said what entitled it to. That entitlement is not free and it is not automatic, and no page you have read so far has priced it. The note is exact about the arithmetic and completely silent about the permission. It said the answer gets walked down one question at a time, and it never said what makes the walking down legal. That debt comes due later on this page. Something smaller is owed first, because page 6 was handed its million and nobody has handed you a fleet.

03The axis is made of answers, and you are the one who draws it

Page 3 already made you halve a hundred and twenty orderings that were never stored anywhere. Five items can be put in order in 5! = 120 ways, and page 3 asked you to name one of those 120 by yes-or-no question alone. It printed the answer as seven, because lg 120 = 6.91 and nobody can ask 0.91 of a question. Not one of those 120 orderings was ever built, or held, or looked at. Page 1 had already handed you the shape of that move in a single clause: every fast algorithm is a way of not enumerating. So halving a space of answers is not new to you here.

What has never been asked of you is where the 120 came from. It came off the problem statement, and page 1 said precisely that — read that number off the problem statement. Every candidate space in this course arrived the same way. One hundred and twenty orderings of five items. 2²⁰ = 1,048,576 subsets of twenty things. One of a million medians. In every one of those, somebody else drew the line, and your work began at the first halving.

How many machines do we rent names no space at all. There is no 5! in that sentence and no 2ⁿ, and nothing in it is a list of anything. So you write one down. The fleet runs from 1 machine to 63. That is the half-open interval [1, 64), and lg 64 = 6 says six probes squeeze it to a single count. Nobody handed you the 63. You chose it, and choosing it is the move this page turns on.

Now look at what mid has become. In page 3's array of fifteen values, lo = 1 and hi = 16 give mid = 8, that 8 is an index, and a[8] is a value somebody stored. On this axis the first probe of [1, 64) gives mid = 32, and 32 is the machine count itself. There is nothing to fetch, because there is no array. The candidate is computed out of two integers, and then tried against the world.

One word needs holding steady, because page 8 spent it on something else. Page 8's axis was a coordinate you had sorted on (one sort bought one axis). Every point on that axis was a row somebody stored, paid for once at n log n. The axis here is the line of candidate answers, and the whole of it is two integers: lo = 1 and hi = 64. Page 8 bought its axis with a sort; this one you draw for nothing, and not one point on it exists.

04Delete one branch from the loop you already own

If nothing is stored, there is nothing to compare against, so what is a step even doing now? Page 3's step fetched a[mid] and held it against the target. Here mid is a machine count you computed a moment ago, and no row holds it. There is nothing at that index, because there is no index and there is no array. What you can still do with a number you invented yourself is ask one question about it. Is 23 machines enough to finish by 06:00? That question comes back yes or no, and it is the only thing a step has left to work with. Call it a probe: one candidate answer goes in, one bit comes out.

Put page 3's loop back on screen, because it is not the loop this page needs and the difference is not cosmetic. That loop hunted for a value in a stored row of fifteen, and it tested equality first, every time. Hunting for 8 landed on 8 at the very first look and stopped there, which page 3 showed you on purpose. So each step asked two questions of a[mid]: is this the target, and if it is not, which side of it am I on? Page 3 priced that worst case at four looks. That is the exact-match search. It is the right tool for a stored row and it does not generalise one inch past one.

So delete the equality branch, and be honest about what the deletion costs before counting what it buys. The cost is the early exit, and it is gone permanently. A boundary search over the 63 machine counts spends log ₂ 64 = 6 probes on every run. That includes the runs where it steps straight over the answer at probe one and keeps going. Six probes, always. What you get back is that each step now asks one question rather than two. On the cheap axis that halves the work per step. On an axis where a probe is a 40-minute trial run, it is the entire game. And the question itself changed underneath you, which is the part worth slowing down for. Exact match asked is it here, and answered with a position or with the word absent. The boundary form asks where does it belong, and answers with a boundary — the first place the world flips.

What survives the deletion is one line, and it is the line everybody reads past: a[mid] >= x. Read it as a comparison and it is furniture, two values and an operator. Read it as a question and it is a test of a single guess: is the target at or after mid? Yes pulls hi down to mid. No pushes lo up to mid + 1. Neither of those two updates cares in the slightest that x lives in an array, or that anything lives anywhere. Swap the line for is 23 machines enough, keep both updates exactly as they are, and the loop does not notice that its world stopped existing.

Which leaves one absence to name out loud, because the section on the loop's invariant is going to lean on it. There is no found branch anywhere in that loop now, and there is nowhere left to put one. A boundary is not a hit, so nothing the loop sees can ever license it to stop early and hand the answer back. It runs its six probes down to a single candidate and returns where the flip is, not what sat there. The comparison was a feasibility test wearing a comparison's clothes, and the array was the special case all along.

05What one probe costs, and which way page 1 pushes you

Page 7 already priced a probe and got sixteen nanoseconds, and the machine set every part of that price. Two nanoseconds to hash, fourteen to fetch. Nothing you wrote moved either number, and nothing you write ever will. Here the probe is whatever your test costs, and you are the one who sets it. It might be one comparison against a value already sitting in cache, or it might be a forty-minute trial run on rented machines, replaying a fixed slice of the night's input at the fleet size you are asking about. The night itself runs seven hours and twelve minutes on forty machines, so the trial is a sample of the job and never the job.

Page 1 priced its probe too, and that page's lesson is the one to be careful with here. Its comparison cost 0.9 ns, and it sat beside a move it could not delete, priced on page 1's own dial at three times a comparison. Cutting 250,000 comparisons down to 8,500 is a 29-fold cut, and it bought 24% of the clock rather than 29 times the speed. The comparisons were never the bill. That reading is exactly right about that machine, and it does not survive the trip to this page.

Put this page's two probes against the same three probe counts. One array comparison is 0.9 ns, twenty of them are 18 ns, and a million tried one at a time are 0.9 ms. One nightly trial run is 40 minutes, twenty of them are 13.3 hours, and a million are 76 years. The dear probe costs 2.7 trillion times the cheap one. Both prices are on this page, and you set both of them when you chose what a single yes-or-no test would run.

Now read the same fraction at each end, because a probe deletes half the space either way. At 0.9 ns, halving a million candidates turns 0.9 ms into 18 ns. It costs you one unwritten sentence about the world, a loop nobody has tested, and an argument in review, and it hands back under a millisecond. Take the scan. At 40 minutes the same halving turns 76 years into 13.3 hours, and no rival budget sits beside it, because the probe is the entire bill.

So the reach is not decided by how large the space is. It is decided by what one probe costs you. Sixty-three candidates and a free probe deserve a loop over all sixty-three. Sixty-three candidates and a forty-minute probe are four hours against nearly two days, and that gap is the whole reason this tool exists. Page 1 taught you to check whether the operation you are cutting is the one paying the bill, and that habit is right. Same fraction, opposite verdict — and the reader who learned page 1 best is the one who now under-reaches.

06Author the claim yourself, then say what the search hands back

You have just been sold this move at its strongest, which is the only honest moment to hand you the switch that breaks it. Every halving you have watched so far was bought with a sentence, and that sentence was never written down anywhere. Here it is, in the words a capacity planner would actually use: if N machines clears the deadline, N+1 clears it too. That is not a line of code. It is a claim about a fleet, a network and a scheduler, and you make it the moment you halve. The claim lives outside the program, because there is nothing in the program for it to be written on.

Say what the claim has to be true of, exactly, because "roughly increasing" is not it. Walk the axis from the smallest candidate to the largest and read your probe's answer at every one of them. The licence is that you see no, no, no, then yes, yes, yes — one crossing, and never a second. Below the crossing every candidate fails, and at or above it every candidate passes. That single transition is the whole of what makes it legal to throw away half the axis on one answer. A yes with a bigger candidate saying no somewhere above it is not a slow case or a rounding artefact. It is the licence revoked.

Fig. 1 hands you the nightly job from the top of this page and asks four things of you before it prints a single number. First, name the thing being halved, because nothing is drawn until you have. Then read three plain facts about a real fleet — sync chatter, a shuffle that outgrows one rack, a cheaper pool that restarts tasks — and say which of them, if any, breaks the sentence above. Then flip a switch on and commit before you run it: right answer, wrong answer, or an error? The commit is made once and stands, but the fleet under it does not, so run all three facts past it and watch the strips diverge. Then set the probe's flakiness to five percent and name the rate of wrong answers you expect. Every readout in the frame stays an em-dash until you have committed to one.

Run it with shuffle fan-out switched on. The first two probes are byte-identical to the honest run: 32 machines clear the deadline, 16 do not. The worlds split at the third probe, which is the quiet one. It asks whether 24 machines are enough, hears an honest no, and throws away everything from 17 to 24 — including 19 and 20, which were alive one probe earlier and were the answer. The last three probes are then perfectly correct about a region that never contained it. Six probes, a clean exit, and the number handed back is 30. The smallest fleet that truly clears 06:00 is 19.

Nothing in that run misbehaved. Every probe answered the question it was asked, truthfully, about the fleet it was actually given. Every probe told the truth. The answer is wrong. Nothing complained. No compiler read the claim, no type carried it, and no test in the repository asserted it, so the loop ran to a clean exit. And 30 against 19 is not a near-miss somebody catches in review. It is eleven extra machines every night, 58 percent over-provisioned, 4,015 machine-nights across a year. The number is precise, it is the right type, and it sits inside the range you drew. It will be 30 again tomorrow night, and every night after that. Reproducibility is what buries it, because a number that jitters gets investigated and a number that never moves gets believed.

Act four gives the honest fleet back and makes the probe merely flaky, so five percent of trial runs answer the wrong way — a pass the fleet did not earn, or a fail it did not deserve. Every lie deletes the true answer permanently, and five percent per probe therefore compounds into 26.5 percent per search: of 200 runs, 53 come back as something other than 23. Look at where they land. The six single-lie outcomes are 33, 16, 25, 20, 22 and 24, and three of those sit below 23, under-provisioning the fleet and missing 06:00 outright. There is also nothing to find afterwards. No two of the six probes ever ask about the same candidate. All six answers therefore agree with each other in every one of the 200 runs, the wrong ones included.

You have met a green wrong answer three times now, once of them on the page you just finished, so the sensation is not the new thing here. The authorship is. Page 1's wrong answer was written by a misread problem statement, and page 8's was written by a library you did not build and could not see into. This one you wrote yourself, in one click, in a sentence that appears in no file. That is the sharp end of the comparison with page 8: an illegal comparator stops answering, inside library code, and gets a ticket, while a false monotonicity claim answers confidently and gets deployed. So take the rule as earned rather than issued. You are not allowed to halve until you can say why the yes cannot come back to no.

07What the claim actually says, and where a true one comes from

The strip is still on screen, so read the claim off it before anybody writes a rule down. In the honest world it reads no across 1 to 22 and yes across 23 to 63, and the only feature that ever mattered was the single place those two words meet. Now read it again for what it does not say. It says nothing about how long the job ran on 30 machines, nothing about whether 40 beat 38, nothing about the shape of anything. The strip carries one bit per candidate, and your licence is a fact about how those 63 bits are arranged. Everything else in the world stays free to be as ugly as it likes.

Two other words get quietly substituted for that fact, and both substitutions cost you. The first is sorted. Nothing here is sorted, because nothing here is stored: you drew the 63 candidates yourself and the program fetched none of them. Sorted is a property data acquires after you pay for it, and page 8 charged 83,805,697 comparisons for it on its 4,000,000-row export. Monotone is a property of an answer, along an axis you invented, and no amount of work makes it true. You can either say why it holds or you cannot.

The second word is smooth, and this one costs you searches you were entitled to run. The cost curve may bounce as much as it likes. Let the nightly job finish at 05:05 on 23 machines, 04:20 on 24 and 05:40 on 25, which is a curve with no manners at all. The predicate still reads yes at all three, because the predicate asks one question with a one-bit answer: did it land before 06:00? The bumps happen entirely inside the word yes, where nothing can see them. A reader who has fused these three words together will refuse legal searches and bless illegal ones, and from the outside both mistakes wear the face of caution.

Page 8 filed this tool under the jump words — range, prefix, sorted — and that filing is correct, and it is half the tool. The other half fires on sentences with no data in them at all. How many machines do we rent? names no collection, no column, no order and no stored thing of any kind, and it is still a binary search. So the tell you are training is not a word about data. It is the shape of the ask, and you met that shape in this page's first four sentences.

There is a repair when the claim fails, and it has to be priced honestly rather than offered as a save. You can monotonise: redefine the probe from does N work to does anything at or below N work, taking the best over the whole prefix. That predicate cannot come back to no, by construction — and it costs the probe exactly the cheapness you were buying it for. On the machine axis, a monotonised probe at 32 is 32 trial runs rather than one, and at 40 minutes each that single probe is 21.3 hours. Written out, the six probes at 32, 16, 24, 20, 22 and 23 come to 137 trial runs. Every probe after the first asks about a prefix the first one already covered, though, so a kept table of results brings that down to 32 distinct runs. Twenty-one hours, then, against the 42 it would take to sweep all 63 candidates outright. The halving still wins, and it has eaten most of the reason you came for it: four hours became twenty-one. Monotonising is not always this brutal. When the prefix best is already in your hand, as a running maximum down a stored array, it is one extra pass and nearly free. The trick turns entirely on which of those two situations you are in.

So where does a true claim come from, when it is real? There are three sources and it is worth being able to name which one you are standing on. By construction: you sorted, so it holds because you paid page 8's price to make it hold, and this is that purchase cashed a second way. By resource inclusion: more budget cannot make a workable plan unworkable. Every plan that runs under budget B still runs under B+1, with the extra left switched off. By hand: you monotonised, and the paragraph above told you what that costs. There is no fourth source. It looked monotone in the graph I plotted is a statement about the candidates you happened to try, and Fig. 1 broke on the ones nobody tried.

Take those three back to Fig. 1's switches and notice that all three switches attack the same source. Sync chatter, the rack boundary at 20 machines, the cheaper pool at 48 — each one says that the extra machine does not sit quietly in a corner. It joins, and joining changes the plan the other machines are running. Resource inclusion holds only while an unwanted resource can be declined, and a distributed job declines nothing. That is not a puzzle-book pathology. It is an ordinary property of the systems you are paid to run, and every one of the three is a fact your team could have stated on request. That is the whole trouble. The second source is the one nobody says out loud, because it feels too obvious to be worth a sentence. So it never becomes one, and it never gets checked. It is not that every claim is dangerous; it is that every unstated one is.

08Two loops that fail differently, and one sentence about lo

Your claim is legal now, so the only thing left between you and the number is the loop. Page 2 already handed you the sentence that makes a loop like this work, on a calendar rather than on a search. Half-open, it said: [2, 6) and [6, 12) both fit, because the room is handed back on the hour. That is a statement about what a boundary means, and the booking code falls out of it without argument. What you were handed for binary search was the opposite shape. A template while lo < hi, a midpoint written lo + (hi − lo) / 2, and no statement underneath either of them. A template you were given instead of a statement is a template you cannot debug. So when it misbehaves there is nothing to reason from, and you permute plus-ones until the tests go green.

Two loops are about to sit on screen, and neither of them runs over a stored row. They run on the same machine-count axis you have been halving all page. lo and hi are counts of rented machines here, and the probe is still the 40-minute trial run. The first loop hangs. When hi is lo + 1 the midpoint rounds down onto lo itself, and an update that assigns lo = mid moves nothing at all. The second loop returns 63, and it returns 63 in two different worlds. One where 63 machines are enough, and one where no number in the range is. It cannot tell you which world you are standing in, and it does not mention that it cannot.

Fig. 2 offers no template to repair either one. You get a single field instead, and it is a fill-in over a fixed grammar rather than a box to type English into. Everything strictly below lo is — known to fail, known to pass, or unknown. And lo and hi are — both still candidates, or a failing floor and a passing ceiling. Three sentences are reachable through those two slots, and each one is a different account of what the loop has already established. The choice is not decoration. The chosen sentence generates the loop: which side moves, whether the bracket is half-open, and what comes back at the end. Then the derived loop is run against every answer the axis could possibly hold.

Fig. 2 enumerates its scenarios rather than sampling them, and the enumeration is small enough to state. 63 possible answers, plus the axis where no candidate works, is 64 runs for every sentence. Two more put the answer outside the bracket you wrote, scored on their own. Say that everything strictly below lo is known to fail. The derived loop starts at lo = 1, hi = 64. It moves hi = mid on a pass and lo = mid + 1 on a fail, and it is right on all 64 in-bracket scenarios. Where nothing works it probes 32, 48, 56, 60, 62 and 63, then returns 64. That is six probes, which is log₂ 64 = 6, and 64 is not a candidate, so the two cases are told apart. Where everything works it probes 32, 16, 8, 4, 2 and 1 and returns 1. The hang and the endpoint miss are gone in the same move, and watching them go together is the only reason this figure exists.

Now the sentence that leaves everything strictly below lo unknown, while lo and hi stay a failing floor and a passing ceiling. Its licence is quieter than it sounds. With nothing established below lo, both boundaries go in on belief rather than evidence. We have always run at least eight machines and it has always been fine, and 63 is the most we can rent, so the bracket goes in as [8, 63). Belief wrote the ceiling too, and wrote it wrong. By this page's own convention, 63 is the most we can rent means [8, 64). The exhaustive run scores the bracket as typed, 56 of 64. Answers 8 through 62 come back right. Answer 63 comes back right by luck, because the excluded ceiling is also the exit value. Answers 1 through 7 all return 8. Seven wrong answers, seven of them identical, every one a confident endpoint, and 56 + 7 + 1 = 64. The last of those is the collision worth staring at. With no candidate working anywhere, this loop returns 63. That is byte-identical to what it returns when 63 genuinely works.

The third sentence says lo and hi are both candidates nobody has ruled out yet. That licenses a closed bracket [1, 63] with no plus one on either side, and it scores 1 of 64. The proof takes two lines and needs no run at all. lo only ever moves onto a mid that failed, so lo is at most a − 1 for every answer a of 2 or more. hi only ever moves onto a mid that passed, so hi is at least a. The gap is one or more and it can never close. So the loop hangs on every answer from 2 to 63 and on the axis where nothing works, which is 63 of 64 scenarios. It terminates on exactly one: a = 1, where nothing fails, lo never moves, and hi walks down 32, 16, 8, 4, 2, 1.

Two things the run makes visible were never the loop's fault, and both of them are yours. The correct loop returns 64 when nothing works, so a seventh probe on whatever came back is what separates an answer from an exit value. That costs 7 × 40 = 280 minutes against 240, a surcharge of 40/240 = 16.7%, and it is the probe nearly every published template leaves out. The other is the bracket. Put the answer outside [lo, hi) and the loop hands back an endpoint with total confidence, because you wrote that bracket and nothing verified it. Those two are authored, the way the monotonicity claim was authored. And the pair the invariant killed — the hang and the endpoint miss — was smaller than it ever looked. They were never two bugs: the interval either failed to shrink, or was allowed to exclude the answer.

09When the axis is real-valued

The loop exited when lo met hi, and on a continuous axis the two of them never meet. Sixty-three machine counts are sixty-three things, so an interval that keeps halving eventually holds exactly one of them and stops. A throttle rate is not like that. Between 340.0 and 340.1 requests per second sits 340.05, and between 340.0 and 340.05 sits another one, forever. The predicate still turns over exactly once, the halving is still legal, and the rate you are hunting still exists. What has gone is found. No probe will ever land on the crossing, and no test of lo against hi will ever come back equal.

So you supply the stopping rule yourself, and the rule is a tolerance you chose. On a temperature axis you name it absolutely: stop once the bracket is narrower than 0.01 °C, because 0.01 °C is what the sensor can resolve. On a price axis you name it relatively: stop at one part in a million. A slack of 0.01 dollars means one thing on a $2 item and nothing on a $2,000,000 trade. Both are claims about how precise this answer has to be. You make the claim before the first probe runs. Nothing in the loop checks this one either.

Write the stop as a fixed count of halvings rather than a condition on width. Halving a starting bracket 1,000 rps wide sixty times divides that 1,000 by 2⁶⁰ = 1,152,921,504,606,846,976, which leaves a bracket 8.7 × 10⁻¹⁶ rps across. Near 340, consecutive doubles are about 5.7 × 10⁻¹⁴ apart, so that bracket is already narrower than the gap between two representable rates. The hundredth halving is not more accurate than the sixtieth, only forty probes slower. And a loop written as while (hi − lo > eps) never exits at all, once eps drops under that floor. The midpoint rounds to an endpoint and the bracket stops shrinking. You are back in the loop that hung a moment ago, for a reason that is nowhere in your code.

Then say what you are actually handing over, because it is not a number. It is an interval. Sixty halvings of that 1,000 rps bracket print 340.0625 rps with a nominal half-width of 4.3 × 10⁻¹⁶ rps, and no double near 340 can hold a bracket that narrow. Halve until the bracket stops shrinking and what you can honestly hand over is 340.0625 rps with a half-width of about 2.8 × 10⁻¹⁴ rps — one representable step, and that second figure is the entire guarantee. Three halvings of the same bracket also print a midpoint, and that midpoint carries 62.5 rps of slack on either side. A colleague reading 340.0625 cannot tell the two runs apart. Ship the midpoint without its width and you have thrown away the only guarantee the method ever gave you.

10And now the rooms where this loses

And now the rooms where this loses. Every refusal so far came from a claim that was not true, and these two rooms are different. The claim is sound, the loop is correct, and the tool is still the wrong one. Here is the trial. You are choosing a fleet size for a nightly job, there are 63 candidate sizes on the axis, and one probe means running the job at one size for 40 minutes. Halving needs six probes, because 63 candidates plus none of them is 64 outcomes and lg 64 = 6. Six probes at 40 minutes each is 240 minutes, which is four hours of the night you were trying to shorten.

Those six probes cannot overlap, and that is the first of the two facts this section is for. The next candidate is not known until the current probe returns, so probe two is waiting on probe one to finish. A sweep has the opposite property. All 63 runs are named before any of them starts, so all 63 can launch at the same instant. That asymmetry is not about speed yet. It is about what you are permitted to schedule.

So parallelism is the dial, and almost nobody turns it before choosing the search. Fig. 3 asks you to put a number down before anything draws. At how many parallel probe slots does binary halving stop being the fastest route to the answer? The options are never, 2, 12 and 63, and whatever you pick is pinned and never marked wrong.

Fig. 3 draws three routes on one clock. With p probes in flight you can cut the live interval into p + 1 pieces per round, so a multiway search needs ceil(log_p+1 64) rounds against binary halving's flat 6. At p = 2 that is ceil(log₃ 64) = 4 rounds, because 3³ = 27 < 64 ≤ 81 = 3⁴. Four rounds is 160 minutes against the halving's 240, so a second probe slot cuts the night by 33 percent. Hold the unit steady here, because the candidate on this axis is itself a machine count: a probe slot is a whole trial fleet of up to 63 machines, not one more machine. The base of the log is your parallelism, and binary search hard-codes it to 2. From the moment you can run a second trial fleet, halving is no longer the fastest thing you can do.

Move the dial to p = 12 and the two readouts openly disagree. The multiway search finishes in 2 rounds of 12, which is 24 probes against binary's 6, and 80 minutes against binary's 240. Four times the probes, one third of the clock. Now price the idleness on that same dial, because it is already on your invoice. Hold 12 probe slots through the serial halving and you provision 12 × 240 = 2,880 slot-minutes. The halving consumes 240 of them, which is 240 / 2,880 = 8.3 percent utilisation, and eleven slots sit on empty track for four hours. The sweep on that same setting takes 6 rounds to cover all 63 sizes, which is 240 minutes, the identical wall clock to serial halving — and it hands back every one of the 63 answers rather than a single boundary point. The log counts probes, and nobody is billed in probes.

The second reveal on the same widget shrinks the axis instead of widening the fleet. Seven compression levels, 90 seconds to test each one. Sweeping all seven costs 7 × 90 = 630 seconds, which is 10 minutes 30 seconds. Halving costs ceil(lg 8) = 3 probes, or 270 seconds, which is 4 minutes 30 seconds. So the entire prize is four saved probes and 360 seconds. You are buying six minutes with an untested loop, an unverified monotonicity claim, and one boundary point where the sweep hands you the whole quality-versus-size curve.

Beside the timeline sits a routing table, seven lines long, each one a destination rather than a mechanism. A hash table when the question is pure membership and there is no axis to order. A heap when you want the top k from a set that is still arriving. An address and a prefix sum when the axis is dense and every query is a range. One parallel round when all the probes can launch together. Just try them all when the whole axis fits on one line. A coarse sweep, or a full stop, when the predicate is not monotone. Fix the probe first when the probe is not a repeatable question at all. Five of those seven turn on the shape of the question, and this page has already taught you to read that shape. The other two are the ones the timeline just drew: a second probe slot changes the base of the log, and a seven-line axis is not worth a claim. Anyone holding the log as a scalar can see neither of these, and both of them are ordinary Tuesdays.

11The seam, and the two facts this page owns

Your claim is right; everything left that can go wrong has nothing to do with the claim. The page turns here, and the turn is worth naming rather than burying in a clause. The licence is settled, the invariant is stated, the tolerance is chosen and the routing is done. What is left is arithmetic and measurement, and there are exactly two of them. Both fire on a search whose monotonicity is perfectly true. That is what puts them on this side of the seam, and neither is a trivia card.

The first is the midpoint you have now written six times. Adding lo and hi before halving forms a sum, and that sum can leave the range the index type holds. A signed 32-bit index stops at 2,147,483,647, so two positions sitting near 1,073,741,824 overflow the instant they are added. The repair never forms the sum at all: lo + (hi − lo) / 2. This one sat in a widely used standard library for about nine years, in code that everybody had read. It survived because the bug needs an array of a billion items, and almost nobody had one. A language that traps the overflow throws on an index nobody can explain. One that wraps quietly hands back a midpoint outside your own interval, and the sentence you chose two sections ago breaks without a word. That is this page's thesis wearing arithmetic.

The second fact is about the probe, and it costs more. A scan that reads one flaky value returns one wrong row and is otherwise correct. A halving that gets one flaky probe deletes half the axis, and nothing in the loop ever goes back to look. The last act of Fig. 1 is where you watched that happen. Five per cent flakiness on the probe, over two hundred searches, does not produce five per cent wrong answers. A single bad probe at step one lands you in a region that never held the answer, and the five probes after it are perfectly correct about the wrong half. So a noisy benchmark is not a nuisance on this page. It is a disqualification.

Which means the repair belongs to the probe rather than to the loop. Pin the machine and take the median of three runs. That turns a forty-minute trial into a two-hour one, and you can afford it, because the search only ever asks six of them. Sixty-three trial runs at forty minutes is nearly two days. Six probes at two hours is twelve, and every one of the six now answers the same way twice. Overflow and a flaky probe both survive a true claim, which is exactly why they belong on the far side of the seam. A scan degrades. A halving does not degrade — it relocates.

12Twenty-five rooms, and the verdict is called first

Every atom on this page has now been named exactly once, so nothing new arrives here. What arrives is Fig. 4, twenty-five situations, and twenty-two of them appear alone. No tell and no verdict, nothing on the card but the sentence somebody would actually say at work. You call it from three: reach, refuse, or something else. Choose something else and you name the destination too, from the seven that sat beside Fig. 3. The other three cards put a search on screen that somebody already wrote, and ask you to name the fault from five. The bar counts down from twenty-five and never up.

The tell is the phrase that gave the situation away, and it sits on the far side of your verdict. It is not hidden, it is absent from the page until your call lands. Open the inspector on any of the twenty-five and there is nothing to read ahead. A tell may only quote words already present in the situation, because a tell carrying the mechanism turns a judgement into a lookup. The seven destinations render only once something else is chosen, so the list cannot be scanned for a match against the sentence. And the score is split by category rather than totalled. A reader who called reach on all twenty-two verdict cards is shown, at rep twenty-five, that they pressed reach twenty-two times. Nothing marks you. A wrong verdict names the replacement and moves on, because the point is the routing.

Fig. 4's census splits four ways. Eleven of the twenty-five resolved to this tool. Six were refusals, five resolved to something else — reaches that looked defensible and were wrong — and three were faults in a search somebody had already shipped. So eleven of twenty-five resolved away from the tool this page teaches, which is 44% of the set. The three diagnoses are not a fourth route off it, because on those the reach was right and the loop was not. The order was part of the spec, and no more than two consecutive cards share a verdict, so position never became the answer. Chapter 7's first drill put twenty-five situations on screen and answered yes to all twenty-five, and this set is ordered so that cannot recur. Half of these sentences carry no data of any kind. That is precisely where a tool filed under searching data never fires.

Two numbers argue here and both are worth printing. A reader who calls reach on all twenty-two verdict cards scores 11, and is wrong eleven times, and every one of those eleven returns a confident number in log time. Blind guessing scores less. Twenty-two calls over three buttons is 7.33, but the five wrong reaches need a destination named from seven as well, which drops their share from 1.67 to 0.24, and the three diagnoses over five faults add 0.60. That totals 6.5 of twenty-five, or 26%. So the reflex beats blind guessing by eighteen points and is still wrong more often than it is right, which is the pairing the category split exists to show you. The sharpest number on the drill is not a probability at all. Five pairs read the same and resolve opposite, so routing on the words alone scores exactly five of those ten, every time.

13The payoff

Walking in, you could already halve a space of answers, because page 3 made you do it with the licence supplied free. Five cards, a hundred and twenty orderings, and the counting argument handed you the right to halve at no charge. Walking out, you know the licence is something you buy. You buy it with one sentence about the world, and you pay before the first probe runs. That moves this tool out of the drawer marked searching data and into the drawer marked deciding a number. The refiling is the whole page, because the new drawer opens on sentences with no data in them at all.

Read how many machines make the nightly job finish by 06:00 and there is no list anywhere in it. You now draw the axis 1 to 63 yourself, and the drawing is the move. You turn find the smallest into is this one good enough, which is page 6's threshold bolt held in your own hand. You take page 3's exact-match loop, delete the equality branch, and know that the edit costs you the early exit and buys you a boundary. Then, before halving anything, you say the claim out loud. If 40 machines finish by 06:00, then 41 machines finish by 06:00 as well, and nothing in your language, your types or your tests can check that sentence for you.

You also know where a true transition comes from, and there are three honest sources. By construction, because you sorted, which is page 8's purchase cashed a second way. By resource inclusion, because every plan that fits a budget still fits a larger one. By hand, because you monotonised, and that repair costs the probe exactly the cheapness you came for. You know the three ordinary facts that break the second source, because each one's strip was counted in front of you and you ran the program against the fleets you built out of them. Sync chatter, a shuffle that outgrows the rack, and a cheap pool that restarts tasks are Tuesdays, not pathologies. And you can name the rooms where the tool loses. Four of the seven destinations you drilled were already yours walking in — a hash table, a heap, an address and a prefix sum, and simply trying them all. The three this page had to give you are the ones nobody arrives holding. One parallel round when the probes can go together. A coarse sweep or a full stop when the predicate wiggles or the curve has a peak instead of a boundary. And fix the probe first, when the probe is not a repeatable question at all.

On the loop itself you state an invariant now, instead of reciting a template you cannot debug. Everything strictly below lo is known to fail, and four obligations fall straight out of that one sentence. The interval must shrink every pass. The answer must never leave it. The candidate that comes back must still be verified with one more probe. And you wrote [lo, hi), so a hi chosen too low is your bug and not the loop's. You also price a probe before you admire the log. Twenty probes at page 1's 0.9 ns comparison is 18 ns, which is a shrug. Twenty probes at this page's 40-minute trial run is 13.3 hours, against 76 years for a million candidates tried one at a time. And the halving is sequential by construction, so twelve probes launched together settle in two rounds where halving needs six.

Two things you already owned change hands here as receipts. Page 6 told you that binary search walks the answer down one yes-or-no question at a time. That sentence sat inside a proof technique, and it is now a tool with a licence attached to it. Page 8 deferred the rest of it here, and the collection reads in one line. A sort buys an address, and this page spends addresses on a space nobody ever allocated. The course's ratio, cashed for this tool, is what one probe tells you over how much of the space it deletes. And the numerator costs you nothing. A million candidates take 20 probes, because log₂ 1,000,000 = 19.93 rounds up to 20; a billion takes 30, and a quintillion takes 60. The space being astronomically large is simply not a problem, because you never build it. The only thing that costs you is the one sentence you have to be able to defend.