Binary Search for Bug Location
What you'll learn: How to use divide-and-conquer techniques to quickly isolate where a bug exists in your code or execution timeline.
The Core Idea
When you know code was working at some point in the past but is broken now, you can apply binary search to find exactly when (or where) the bug was introduced. Instead of checking every change linearly, you check the middle of the range, determine if the bug exists there, and eliminate half the possibilities—then repeat.
This works for:
- Commit history: Testing the midpoint between a known-good and known-bad commit
- Execution flow: Checking intermediate states in a long process
- Code sections: Testing whether a bug occurs before or after a certain line
How It Works
Imagine you have 100 commits. You know commit #1 worked, commit #100 is broken. Testing all 100 linearly takes 100 checks. Binary search:
- Test commit #50 — is the bug present?
- If yes, the bug is between #1 and #50. Test #25 next.
- If no, the bug is between #50 and #100. Test #75 next.
- Repeat, halving the range each time.
This reduces 100 checks to approximately 7 (log₂ 100 ≈ 6.6).
Practical Application
Git provides git bisect specifically for this:
- Mark a known-good commit
- Mark a known-bad commit
- Git checks out the middle commit automatically
- You test and mark it good or bad
- Repeat until the culprit commit is found
The same logic applies when stepping through code execution: test assertions at midpoint functions rather than tracing every line sequentially.
Key Takeaway:
Binary search for bug location cuts debugging time logarithmically by systematically eliminating half the search space with each test.