Halving turns 64 builds into six questions
One-line summary
Binary search is not a tool but a procedure. The moment you make it possible for a machine to tell good from bad, a history of 64 builds or 4096 rows of data shrinks to six and twelve probes.
Why this is needed
There are two sentences heard most often in the field. "It worked until last week" and "it only dies on the file that came in yesterday." They sound like completely different statements, but the structure is the same. Somewhere there is one boundary; before it is fine and after it is not. What we are looking for is that boundary.
The most natural way to find a boundary is to look one by one from the front. Running 64 builds one by one takes 64 runs in the worst case, and at 30 seconds each that is 32 minutes. Feeding 4096 rows of data in one line at a time is 4096 runs. And the customer's contact is waiting next to you.
If you halve instead, the numbers change. With 63 candidates it is six probes, with 4096 it is twelve, and even with a million it is twenty. Each time the candidates double, the count grows by one. This property changes the nature of the work in the field — the larger the data grows, the wider the gap with sequential search gets.
How it works
For binary search to work, three things must hold.
First, a machine must be able to judge. "It looks a bit off" is not a judgment. The judge must be a program that takes an input and produces either good or bad, and if a procedure where a person looks at the screen and tilts their head gets mixed in, you cannot repeat it twenty times. This is why git bisect has the form git bisect run <스크립트> (where the placeholder is the script). In that convention, exit code 0 means good, 1 through 124 mean bad, and 125 means cannot judge (skip). Our lab uses the same promise.
Second, the property must be monotonic. Everything before the boundary must be good and everything after it bad. If the history was fixed midway and then broke again, binary search gives you "some bad build," not "the first build that went bad." The same goes for the data side. The case where one row kills it alone is monotonic, but the case where it dies only when two rows are together is not monotonic: the moment you split the pieces, the two get separated and both sides pass.
Third, the candidates must have an order. Builds have a time order, and files have a row order. For candidates without an order (twenty configuration items), the same principle is used not as bisection but as grouping them and turning off half at a time.
Python's standard library bisect module provides functions that find the position of a value in a sorted array. What we do is a search that calls a judge instead of an array, and the skeleton is the same. You keep the known good position as lo and the known bad position as hi, and ask about the middle, pulling one side in, until only one step remains between them. With n candidates, the number of questions needed is log2(n) rounded up — each question halves the candidates, so to get n down to 1 you count how many times you multiply 2 to reach n.
후보 63개 → 6번 후보 4096개 → 12번
후보 100만개 → 20번 후보 10억개 → 30번
Cannot judge is a special value. Builds that do not start, builds missing a dependency module, and builds from a day when the network happened to be down all belong here. If you count these as "bad," the boundary gets pushed forward and you point at the wrong build as the culprit. So you add a third value, and when you meet it, you step aside to a neighbor and ask again. If the whole interval cannot be judged, you do not point at a single build and report the remaining interval as it is. Having narrowed the range is also a result.
What you see in the field
First, starting the search before building the judge. If you run the middle build and judge by eye, saying "hmm, it seems slow, sort of," then after about ten probes you cannot remember which side you called good. If you build the judge first, the search is just a loop.
Second, finding the boundary and not verifying it. The search is logarithmic, but verification is linear. The cost of running all the builds after the boundary to confirm they are all bad is the same as having done a sequential search from the start. You still have to do it once — because on a non-monotonic history, binary search quietly gives a wrong answer. If you are short on time, at least confirm twice: that the boundary build is bad and the one before it is good.
Third, losing the header on the data side. If you strip the header while cutting a CSV in half, the latter chunk reads its first row as column names and fails for the wrong reason. Then every chunk becomes bad and the search points to row 1. Always attach the header when making chunks.
Fourth, not counting the probes. If you write only "found by binary search" in the report, the customer does not know the value of that procedure. If you write "narrowed 4096 candidates in 12 probes," the next time someone says let's use the same procedure again. The numbers sell the method.
What really matters in practice
- The judge comes first. If a machine cannot tell good from bad, the search cannot begin.
- Do not fold cannot-judge into bad. Add a third value and step aside to a neighbor.
- Doubt monotonicity. After finding the boundary, verify at least twice, and exhaustively if possible.
- Record the count. You must also write how many sequential probes it would have been for the procedure to sell itself.
What you will do in the next lab
With the customer's 64 builds and 4096 new input rows in hand, you first build a judge that separates good, bad, and cannot judge. With that judge you halve the history to find the first build that went bad, and attach a way to step aside when you meet a build that does not start. You apply the same principle to the data to find the row that kills the loader in twelve probes, verify exhaustively that the boundary really is a boundary, and then report it on one page along with how many probes a sequential search would have taken.