A regression appears in the current build, but the same behavior worked two weeks ago. Since then, the team has merged 80 changes. Reading all 80 diffs is possible, but it is slow and gives every change equal attention even though only one boundary in history matters: the point where the behavior changed from working to broken.

When revisions are ordered and you can classify a revision reliably as good or bad, you can search that history with the same idea as binary search. Test a revision near the middle. Its result tells you which half can still contain the first bad revision. Repeat until only the transition remains.

This article explains the mental model, the conditions that make it valid, and how to use it without being misled by flaky tests, broken historical builds, or regressions that do not follow a simple good-to-bad sequence.

Search for a boundary, not a suspicious diff

Suppose eight revisions are ordered from oldest to newest:

A  B  C  D  E  F  G  H
G  G  G  G  B  B  B  B

G means the behavior is good and B means it is bad. The useful answer is not merely that revision H is broken. You already know that. The useful answer is that the transition occurs between D and E.

If each revision represents one change, E is the first revision that exhibits the regression. That sharply narrows the investigation: inspect what changed from D to E, then explain how that change produced the observed failure.

The key assumption is visible in the sequence above. For the property you are testing, history has one boundary: good revisions come before bad revisions. Binary search depends on that ordering.

Imagine you know revision A is good and revision H is bad. Instead of checking B, then C, then D, test a revision near the middle, such as D.

If D is good, then A through D cannot be the first bad revision. The remaining candidates are:

D  E  F  G  H
G  ?  ?  ?  B

Now test near the middle of that smaller interval, perhaps F.

If F is bad, then G and H are no longer relevant to finding the first bad revision. The boundary must be between D and F:

D  E  F
G  ?  B

Test E. If it is bad, the transition is now known:

D  E
G  B

Three checks classified the boundary among eight revisions. A linear scan from the oldest known-good revision could have required many more checks.

The benefit grows with the search range. Each reliable middle result removes roughly half of the remaining candidates. That is why the number of checks grows logarithmically rather than linearly when the assumptions hold.

The search is only as reliable as the classification rule.

A vague rule such as “the application seems fine” makes each step subjective. Prefer a focused observation tied directly to the regression:

Given an invoice with a 10% discount,
when the total is calculated,
the result must be 90.00 for a subtotal of 100.00.

A revision is good if that check passes and bad if it fails in the specific way under investigation.

This matters because historical revisions may have unrelated defects. Suppose an old revision cannot send email because a development credential has expired. If the regression concerns invoice totals, email failure should not automatically make that revision “bad.” Your classification should answer one narrow question: does this revision exhibit the regression?

An automated test is often the most repeatable classifier, but it is not required. A deterministic script, a small request against a local service, or a precise manual procedure can work. What matters is that repeated checks of the same revision normally produce the same classification.

Start with proven endpoints

Before halving the range, verify both ends.

You need:

  • a known-good revision where the behavior works;
  • a known-bad revision where the regression is present.

Do not rely only on memory that “it worked around last month.” Test the supposed good endpoint with the same classification rule. If it is already bad, the regression started earlier than your range. If the supposed bad endpoint passes, you may be reproducing a different condition or dealing with nondeterministic behavior.

Verifying endpoints prevents a common debugging mistake: performing a precise search inside the wrong interval.

Keep the environment comparable

A historical revision does not run in a historical world. It may execute today against newer dependencies, configuration, test data, operating-system packages, or external services.

That creates an important distinction:

source revision changed

is not the same as:

only source revision changed

If you want to attribute the regression to a code change, keep other relevant inputs as stable as practical. Use the same test data, configuration, dependency lock files, and execution procedure across revisions. Avoid calling mutable external services when a local or controlled substitute can answer the regression question.

Sometimes the environment itself is the suspected cause. In that case, source history may be the wrong search dimension. You may need to search deployment versions, configuration changes, dependency versions, or data migrations instead. The binary-search mental model still applies if those candidates are ordered and can be classified reliably.

Treat untestable revisions as missing information

Real histories are not perfectly testable. An intermediate revision may not compile with your current toolchain. A fixture may be missing. A migration may assume infrastructure that no longer exists.

Do not label such a revision good or bad merely to keep the search moving. “Cannot test” is a third state.

Suppose the current interval is:

C  D  E  F  G
G  ?  X  ?  B

where X means revision E cannot be classified. You can test another revision such as D or F to gain information. The search may become less efficient because you cannot always split the candidate range evenly, but preserving truthful classifications is more important than preserving perfect halving.

If many revisions are untestable, repair the test harness only if doing so is cheap and does not alter the behavior you are measuring. Otherwise, switch to a coarser search unit, such as releases or deployment artifacts that can still be reproduced.

Flaky behavior breaks the core assumption

Binary search assumes that a revision has a stable answer. A flaky test can produce a sequence that appears to look like this:

A  B  C  D  E  F
G  B  G  B  B  G

There is no single trustworthy boundary in that observation. A middle result cannot safely eliminate half the range because rerunning the same revision might produce the opposite result.

If the classifier is nondeterministic, address that before trusting the search. Depending on the problem, that may mean fixing the flaky test, controlling time and randomness, isolating external services, or running repeated trials and using a deliberately defined statistical criterion.

Repeated trials are not a universal fix. If a failure occurs with low probability, a few passing runs do not prove that a revision is good. The important point is to recognize that you are no longer doing ordinary binary search over deterministic states.

Not every regression is monotonic through history

A second failure mode is subtler. A behavior can break, be fixed, and then break again:

A  B  C  D  E  F  G
G  G  B  B  G  G  B

This history has multiple transitions. Knowing that A is good and G is bad does not guarantee that binary search will find the earliest historical break. It can find a boundary consistent with the checks it performs, but the simple “one good region followed by one bad region” model is false.

This often happens when the symptom is broad. For example, “checkout fails” could describe several unrelated defects introduced at different times.

Narrow the classifier to the specific behavior you are investigating. If multiple independent changes can create the same observation, decide which question matters. You may want the change responsible for the current regression, not the first time any similar symptom appeared.

The first bad revision is evidence, not the full diagnosis

Finding the boundary is a localization technique. It does not prove that every changed line in the first bad revision is causal.

A revision may contain several edits. The failure may also depend on data, configuration, or an interaction with an earlier dormant change. After locating the boundary, inspect the delta and form a causal explanation.

A useful follow-up sequence is:

  1. Identify which changed behavior could affect the failing path.
  2. Reproduce the failure with the relevant change present.
  3. Remove or neutralize that change when practical and confirm that the failure disappears.
  4. Add a focused test that captures the intended behavior before fixing the defect.

This turns “revision E is first bad” into a stronger statement: “this change altered this condition, which caused this observable failure under these inputs.”

Search the smallest meaningful history

Binary search is most valuable when the candidate range is large enough that checking every revision would be wasteful. It is unnecessary when there are only two or three plausible changes and reading them is faster than rebuilding old versions.

You can also reduce the range before searching. If monitoring shows that the behavior worked in Monday’s deployment and failed in Tuesday’s deployment, start there rather than searching six months of repository history. If a subsystem has an independent release history, search that history instead of unrelated application commits.

Choose the ordered sequence that most closely represents the changes capable of producing the regression.

When binary search is a good fit

Use this technique when you can establish a known-good point, a known-bad point, an ordered set of candidate changes, and a reasonably deterministic test for the regression. It is especially useful when the interval contains many revisions and each individual diff would take meaningful time to investigate.

Use a simpler approach when the candidate set is tiny, when one recent change is already strongly implicated by direct evidence, or when testing historical revisions costs more than inspecting the few relevant changes.

Choose a different debugging strategy when the failure depends on nondeterministic timing, changing production state, or several independent transitions that cannot be represented by one good-to-bad boundary. In those cases, first isolate the condition that makes the result reproducible or search a more appropriate dimension.

Conclusion

When a regression exists somewhere in an ordered history, do not begin by treating every revision as equally suspicious. First define a precise good-or-bad check and verify the endpoints. Then test near the middle and use each result to discard the half that cannot contain the transition.

The technique is powerful because it converts debugging from broad inspection into a sequence of evidence-producing questions. Its limits are equally important: flaky classifications, untestable revisions, changing environments, and multiple good-to-bad transitions can invalidate the simple model.

Use binary search when history contains one meaningful boundary. Once you find that boundary, finish the job by explaining and testing the causal change.

Software Engineering Debugging Testing Engineering Workflow