Narrowing by Halves

What two passing halves tell you

Lesson 7-2's minimization sometimes cuts an input in half and finds that both halves pass. That is not a dead end, because the failure needs something about the combination, which is itself a strong clue.

Every experiment teaches something, which is lesson 7-1's whole point. If neither half fails alone, the bug involves interaction between parts, and the usual candidates are size itself, an item that spans the cut, or an ordering that only appears in the full input.

You adjust how you shrink rather than abandoning the technique. Cutting at a different point, removing one element at a time near the boundary, or keeping the size and simplifying the values are all reasonable next moves, and the halving strategy stays.

Bisection, the logarithm on your side

The halving trick from lesson 7-2 generalizes into the most powerful search move in debugging, bisection. Whenever a bug hides somewhere in an ordered range, test the midpoint and throw away the half that cannot contain it.

One definition first. Professional teams keep code in version control, a tool that records a snapshot of the whole project every time someone finishes a change. Each recorded snapshot is a commit, the standard tool is Git, and you can check out any old commit to run the project exactly as it was at that moment. Git gets its own course later, and what matters here is that commits form an ordered timeline, since ordered is all bisection needs.

The move applies to three different ranges:

• history: it worked last month, 1,000 commits ago. Check out the middle commit, run the failing test, and 1,000 suspects become 500, then 250
• code: comment out or bypass half a pipeline to learn which half hides the fault
• input: exactly what you did to the median list

Each test halves the suspects, so n suspects need only log₂(n) tests. That means 1,024 commits fall in 10 checks and a million in 20.

Git automates the history version as git bisect. You mark one commit good and one bad, Git checks out midpoints, and you answer good or bad until it names the first bad commit.

A simulated git bisect

Commits 1 to 16, with commit 1 known good and 16 known bad. is_broken plays the role of running your test at a checked-out commit, and four questions find the exact first bad commit.

def is_broken(commit):
    return commit >= 11

low, high = 1, 16
while high - low > 1:
    mid = (low + high) // 2
    if is_broken(mid):
        print(f"commit {mid}: broken, first bad is at or before {mid}")
        high = mid
    else:
        print(f"commit {mid}: good, first bad is after {mid}")
        low = mid
print("first broken commit:", high)

Output

commit 8: good, first bad is after 8
commit 12: broken, first bad is at or before 12
commit 10: good, first bad is after 10
commit 11: broken, first bad is at or before 11
first broken commit: 11

In real life is_broken(mid) is you running the failing test at that commit, or git bisect run doing it automatically. The >= 11 here stands in for a change that broke something and stayed broken afterward.

The loop maintains an invariant worth stating plainly: low is always known good and high is always known broken. Each answer moves one of them to the midpoint, never both, and the loop stops when they are adjacent, at which point high is the first bad commit by definition.

The stopping condition is high - low > 1 rather than low < high, and that difference matters. Waiting for them to meet would test the same commit forever, since the midpoint of two adjacent numbers is the lower one.

Four tests for 16 commits matches log₂(16), which is the arithmetic the lesson promised. Note that bisection requires the property to be monotonic, meaning that once broken it stays broken, and a bug that comes and goes across history breaks the assumption that half the range can be discarded.

The same loop on a bigger haystack

1,024 commits and an unknown break point, with a step counter added so the log₂ prediction can be checked.

def is_broken(commit):
    return commit >= 250

low, high = 1, 1024
steps = 0
while high - low > 1:
    mid = (low + high) // 2
    steps += 1
    if is_broken(mid):
        high = mid
    else:
        low = mid
print("first broken commit:", high)
print("steps:", steps)

Output

first broken commit: 250
steps: 10

The loop is unchanged from the previous block apart from steps += 1 right after computing mid, and the invariant still holds, with low good and high broken, so the answer is high once they are adjacent.

log₂(1024) is 10, so exactly 10 midpoint tests is the predicted and observed count. Predicting before running is worth doing, because a step count far above the prediction usually means the loop is not actually halving, and one far below means the range was smaller than you thought.

Note that 250 is nowhere near the middle of the range, and the step count does not care. Bisection's cost depends on the size of the range rather than on where the answer sits inside it, which is what makes the worst case and the typical case the same here.

The linear alternative is the comparison that makes the point. Checking commits one at a time from the start would take 249 tests to reach the same answer, and at even one minute per checkout and test run, that is the difference between ten minutes and four hours.

Bisecting a million commits

A regression somewhere in the last 1,000,000 commits, which a monorepo, a single repository holding all of a company's code, really can accumulate, takes about 20 bisection steps.

2²⁰ is about 1,048,576, so 20 good-and-bad answers pin one commit out of a million. That logarithm is why bisection beats reading diffs, because the haystack size barely matters once you can ask a yes-or-no question about any midpoint.

The scaling is worth seeing as a table, since the numbers are hard to believe otherwise:

Doubling the history adds exactly one step. That is the practical meaning of a logarithm, and it is why teams with enormous repositories still find regressions in an afternoon.

The real cost moves elsewhere, which is worth knowing before you try it. Each step needs a check-out, a build, and a test run, so 20 steps at five minutes each is under two hours of mostly waiting, and the expensive requirement is a reliable automated test that answers good or bad without a human judging it.