The binary search mental model — O(log n) and the step counts for typical histories

A bisect session is a binary search over a range of commits. The search begins with the range between the known-good and known-bad boundaries and halves it on each step: each midpoint the engineer marks good halves the remaining candidate set, each midpoint marked bad halves it from the other side. The number of steps the bisect takes is therefore predictable from the size of the candidate set, not from the contents of the commits. This lesson quantifies the search so an engineer can predict how long a bisect will take before starting it.

O(log n) — the complexity bound

The best-case cost of a bisect session over N candidate commits is ceiling(log2 N). The log is base 2 because each step halves the range: after one step the range has at most N/2 candidates, after two steps at most N/4, after k steps at most N / (2^k). The search terminates when the range has one commit left, which is when N / (2^k) = 1, which is when k = log2 N. The ceiling is because partial halvings still require a step.

# ceil(log2 N) for a few values of N
#    N =       1 => 0 steps
#    N =       2 => 1
#    N =       4 => 2
#    N =       8 => 3
#    N =      16 => 4
#    N =      32 => 5
#    N =      64 => 6
#    N =     100 => 7
#    N =     128 => 7
#    N =     256 => 8
#    N =     512 => 9
#    N =    1024 => 10
#    N =   10000 => 14
#    N =  100000 => 17
#    N = 1000000 => 20

The practical reading: a 100-commit history takes at most 7 steps. A 1000-commit history takes 10. A 10000-commit history takes 14. A 100000-commit history takes 17. The number of steps grows logarithmically with the history size; doubling the history adds one step, not two.

Step counts for typical infrastructure repositories

The scale of a typical infrastructure repository sits between small and medium. A young Terraform monorepo might have a few hundred commits between the first release and the current state; an Ansible playbook repository used for years might have a few thousand; a kernel fork might have tens of thousands.

flowchart TB
    subgraph STEPS["Steps to bisect"]
        S1["1 step - 2 commits"]
        S2["2 steps - 3-8 commits"]
        S3["3 steps - 9-24 commits"]
        S4["4 steps - 25-72 commits"]
        S5["5 steps - 73-216 commits"]
        S6["6 steps - 217-648 commits"]
        S7["7 steps - 649-1944 commits"]
        S8["8 steps - 1945-5832 commits"]
        S9["9 steps - 5833-17496 commits"]
        S10["10 steps - 17497-52488 commits"]
    end

For an infrastructure engineer the implication is clear: the bisect is fast even on large histories. A regression in a 5000-commit history takes at most 13 bisect steps. If each step takes 30 seconds of CI run time, the entire investigation is under seven minutes. The bisect is not the bottleneck; the test is.

Why some sessions take more than the minimum

The minimum step count assumes every midpoint the engineer encounters can be tested. In practice, some midpoints cannot be tested cleanly: a midpoint is a merge commit whose tree does not build cleanly on its own, a midpoint introduces a flaky test, a midpoint is a force-pushed branch tip that no longer checks out. When a midpoint cannot be tested, the engineer’s recourse is git bisect skip, which removes the midpoint from the candidate set and continues the search around it.

# A skip mid-session
git bisect run ./ci-test.sh
# running ./ci-test.sh
# Bisecting: 47 revisions left to test after this (roughly)
# running ./ci-test.sh
# Some revisions cannot be tested, skipping: a3f1c2d bump provider
# running ./ci-test.sh
# ...
# 7e89b40 is the first bad commit

Each skip adds at least one step to the session. In the worst case, a long sequence of adjacent skips can degenerate the session into a near-linear scan. The skip mechanism exists for a reason - it is better to skip and continue than to abort the session - but a session with many skips is a session that is slower than the minimum.

Merge commits and the range topology

The minimum-step count assumes a linear range between the bad and good boundaries. A linear range is what the engineer gets when the boundaries are on the same linear history (no diverging branches between them). When the boundaries are on diverging branches, the range is the merge base plus the commits on both branches - a “trefoil” topology that bisect walks as a set, not a line.

# A linear range: one branch, two endpoints
git rev-list --count v3.4.0..HEAD
# 247

# A trefoil range: two endpoints on diverged branches
git rev-list --count main..feature
# 412
# bisect counts all candidates reachable from one boundary and
# not from the other

In a trefoil, the bisect algorithm walks the candidate set as a set and picks midpoints that narrow the set on each step. The step count is still O(log N), but N is the size of the union of both branches’ unique commits, not the size of either branch alone. Engineers who bisect across a feature branch and the trunk it diverged from should expect more candidates than a linear scan would suggest.

Production discipline

1. Predict the step count before starting. Take the size of the candidate range (git rev-list --count <good>..<bad>) and compute ceiling(log2 of that number). The prediction is the number of test cycles the engineer is committing to.
2. Choose boundaries that minimise the candidate range. The closer the good boundary is to the bad boundary, the faster the bisect. If the engineer knows the regression appeared in the last week, use a known-good from a week ago, not from a year ago.
3. Treat a skip-heavy bisect as a test problem. A bisect that accumulates skips is signalling that the test does not handle every commit cleanly. Fix the test; do not keep skipping.
4. Use git bisect visualize when the topology is unclear. Bisect’s printout of candidate counts assumes the engineer can read the candidate set. When the candidate set is a DAG, the visualize command (covered in lesson 04) shows the topology the engineer is actually searching.

Cross-course references

• CI/CD Pipeline Patterns - Part II (AlgorithmicComplexity) covers the same O(log n) mental model for bisect-style searches, including the parallelisation patterns that bisect cannot use (bisect is sequential; CI matrices are parallel).
• Linux for Production Sysadmins - Part XXIV (BisectingKernels) gives real step counts for kernel bisects: a typical regression takes 12 to 18 steps against a 1.2-million-commit history, exactly the O(log n) prediction.
• Performance Engineering for Production Sysadmins - Part III (Search) covers binary search as an algorithmic pattern beyond Git; bisect is the version-control-domain instance of the same idea.

Quiz