Bisect

Binary Search for Bugs

git bisect uses binary search to find the specific commit that introduced a bug. Given a known-good commit and a known-bad commit, it checks out commits between them, narrowing the range by half each iteration until it identifies the exact culprit.

Why Manual Debugging Fails

When a bug is discovered in production, you may need to search through hundreds or thousands of commits to find when it was introduced. Linear search (checking each commit one by one) has $O(n)$ time complexity. Binary search reduces this to $O(\log_2 n)$ :

Commits to search	Linear steps	Binary steps
100	100	7
1,000	1,000	10
10,000	10,000	14
100,000	100,000	17

Basic Usage

## Start a bisect session
$ git bisect start

## Mark the current commit as bad (bug is present)
$ git bisect bad

# Mark a known-good commit
$ git bisect good v2.5.0

# Git checks out a commit halfway between v2.5.0 and HEAD
# Build and test the code...
# If the bug is present:
$ git bisect bad
# If the bug is NOT present:
$ git bisect good

# Repeat until git identifies the culprit:
# a3f2b1c0 is the first bad commit
# commit a3f2b1c0
# Author: Developer <dev@example.com>
# Date:   Mon Jun 2 10:00:00 2025
#
#     Refactor authentication module

flowchart TD
    A["git bisect start"] --> B["git bisect bad HEAD"]
    B --> C["git bisect good v2.5.0"]
    C --> D["Git checks out<br/>midpoint commit"]
    D --> E{"Test:<br/>is bug present?"}
    E -->|Yes| F["git bisect bad"]
    E -->|No| G["git bisect good"]
    F --> H{"Range<br/>narrowed to 1?"}
    G --> H
    H -->|No| D
    H -->|Yes| I["Culprit identified!<br/>git bisect reset"]

    style I fill:#e8f5e9

One-Line Syntax

# Equivalent to the above, in a single command
$ git bisect start HEAD v2.5.0

Automated Bisect

For bugs that can be detected by a script (exit code 0 = good, non-zero = bad), you can automate the entire process:

# Define a test script
$ cat > test_bug.sh << "EOF'
#!/bin/bash
make build
./run_tests --suite auth
EOF
$ chmod +x test_bug.sh

# Run automated bisect
$ git bisect start HEAD v2.5.0
$ git bisect run ./test_bug.sh

# Git automatically tests each midpoint and identifies the culprit
# a3f2b1c0 is the first bad commit

The run command will:

Check out each midpoint commit.
Run the script.
Mark the commit as bad if the script exits non-zero, good if it exits zero.
Continue until the range is narrowed to one commit.

system state. Clean build artifacts, use a fresh database, etc. Otherwise, you may get false positives from stale state.

Bisect with Skipped Commits

Some commits may not build (e.g., due to a missing dependency or a known compilation error). You can skip them:

$ git bisect skip
# Git adjusts the search range to avoid this commit

If many commits cannot be tested, bisect may not find a single culprit. It will report the range:

There are only 'skip'ped commits left to test.
The first bad commit could be any of:
a3f2b1c0...c1d2e3f4
b7e9d4f5...d4e5f6a7

Terminating a Bisect Session

# Reset to the original branch after finding the culprit
$ git bisect reset

# Reset to a specific branch
$ git bisect reset main

git bisect reset restores the branch you were on before starting the bisect.

Bisect Best Practices

1. Use Good/Bad Markers Strategically

Bad: The commit where the bug is confirmed present ( HEAD or a specific release tag).
Good: The most recent commit where the bug is confirmed absent. The closer this is to the bad commit, the fewer iterations needed.

2. Write Reproducible Test Scripts

#!/bin/bash
set -e

# Build from scratch (no cached artifacts)
make clean
make -j$(nproc)

# Run the specific test that catches the bug
./run_tests --suite auth --fail-fast

3. Bisect in CI/CD

Integrate bisect into your CI pipeline to automatically identify regressions:

# In your CI job, after a test failure:
$ git bisect start HEAD $PREVIOUS_GREEN_COMMIT
$ git bisect run make test
$ git bisect reset

4. Combine with `git blame`

Once you identify the culprit commit, use git blame to see which lines were changed:

# Show which commit changed each line in a file
$ git blame src/auth.c

# Show which commit changed a specific line
$ git blame -L 42,42 src/auth.c

Then examine the full commit:

$ git show a3f2b1c0

Common Pitfalls

Confusing authentication (who you are) with authorisation (what you can do) in security contexts.
Mixing up Big O, Big $\Omega$ , and Big $\Theta$ notation. Big O is an upper bound, not necessarily tight.
Neglecting to normalise database designs, leading to data redundancy and update anomalies.
Writing pseudocode that is too language-specific rather than using standard algorithmic constructs.

Summary

The key principles covered in this topic are linked in the sub-pages above. Focus on understanding the definitions, applying the formulas or frameworks, and evaluating strengths and limitations of each approach.

Worked Examples

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.

Intuition

Bisect is like playing “20 Questions” with your commit history. You start with a range of commits and ask “Is the bug here?” If yes, you eliminate the second half; if no, you eliminate the first half. Each question cuts the search space in half, so you find the culprit in logarithmic time. It is like finding a specific page in a book by repeatedly asking “Is it in the first half?” instead of reading every page. The key insight is that bisect leverages the fact that commits are ordered - if a bug is introduced at commit X, it must be present in all commits after X. This monotonic property makes binary search applicable.

Cross-References

Reflog - How to recover if bisect leads to unexpected results
Submodules - Managing external dependencies that complicate bisect

Mark this page as reviewed