Course contentsShow
← Software Engineering
Lesson 1713 of 1,93350. Debugging and TroubleshootingFree lesson

Binary Search for Bug Location

Use divide-and-conquer techniques to efficiently narrow down where a bug occurs in code or execution flow.

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:

  1. Test commit #50 — is the bug present?
  2. If yes, the bug is between #1 and #50. Test #25 next.
  3. If no, the bug is between #50 and #100. Test #75 next.
  4. 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.