Scrolls
3 min read
On this page

Bisection & Elimination

When you have a large problem space, the fastest way to find the cause is to cut it in half repeatedly. Instead of checking everything one by one, divide the possibilities into two groups, test one group, and eliminate whichever half does not contain the problem. Each step removes half of the remaining possibilities.

The Everyday Version

Finding a Bad Light Bulb

A string of 16 holiday lights is not working. One bulb is bad, but which one?

Approach A: Check one at a time
- Test bulb 1. Works.
- Test bulb 2. Works.
- Test bulb 3. Works.
- ...continue until you find the bad one
- Worst case: 16 tests
- Average: 8 tests

Approach B: Bisection
- Disconnect the string at the middle (after bulb 8)
- Test the first half (bulbs 1-8). Works? Or not?
  → First half works → Bad bulb is in bulbs 9-16
- Test the middle of that half (bulbs 9-12)
  → Does not work → Bad bulb is in 9-12
- Test bulbs 9-10
  → Works → Bad bulb is in 11-12
- Test bulb 11
  → Works → Bad bulb is 12

Total tests: 4 (instead of up to 16)

This is the power of bisection: each test eliminates half of the remaining possibilities. For 16 items, you need at most 4 tests. For 1,000 items, you need at most 10 tests.

Finding a Tripped Circuit Breaker

The power is out in part of your house, but you do not know which circuit breaker tripped.

Your breaker panel has 16 breakers.

One-by-one approach:
- Flip each breaker off and on, check the room
- Up to 16 trips to the breaker panel

Bisection approach:
- Turn off all breakers
- Turn on the first 8 → Does the problem area have power?
  → Yes → The tripped breaker is in the first 8
  → No → It is in the second 8
- Turn on half of the remaining group
- Continue halving until you find the one breaker

4 rounds of testing instead of 16.

Finding When Milk Went Bad

You bought milk last week and it smells off. When did it go bad?

You bought it 7 days ago.

One-day-at-a-time (mental reconstruction):
- Was it fine on day 1? Probably.
- Day 2? Probably.
- Day 3? I think so...
- This is slow and unreliable.

Bisection (if you had a time machine):
- Was it fine on day 4 (the middle)?
  → Yes → It went bad sometime between day 4 and day 7
- Was it fine on day 6?
  → No → It went bad between day 4 and day 6
- Was it fine on day 5?
  → Yes → It went bad on day 6

In practice, you cannot test milk retroactively,
but the principle applies to anything where you can
check a midpoint: recipes, processes, timelines.

The Guessing Game

The classic demonstration of bisection: guess a number between 1 and 100.

Optimal strategy:
Guess 50 → "Too high"
Guess 25 → "Too low"
Guess 37 → "Too high"
Guess 31 → "Too low"
Guess 34 → "Too high"
Guess 33 → "Too low"
Guess 33.5... → Must be 33 or 34
Answer found in 7 guesses (out of 100 possibilities)

Random guessing would take up to 100 tries.
Linear search (1, 2, 3, 4...) takes up to 100 tries.
Bisection takes at most 7 tries for 100 items.

How the math works:
- Each guess eliminates half the possibilities
- Start: 100 items
- After guess 1: 50 items
- After guess 2: 25 items
- After guess 3: 13 items
- After guess 4: 7 items
- After guess 5: 4 items
- After guess 6: 2 items
- After guess 7: 1 item → found it

The number of steps = log2(N)
- 100 items: about 7 steps
- 1,000 items: about 10 steps
- 1,000,000 items: about 20 steps
- 1,000,000,000 items: about 30 steps

Connecting to Technology

Git Bisect

Git bisect is bisection applied to version control. Something broke, and you need to find which commit introduced the bug.

Scenario:
- The app worked last Monday (commit #200)
- The app is broken today (commit #250)
- 50 commits in between
- Which one broke it?

Without bisection:
- Check commit 201. Works.
- Check commit 202. Works.
- ...check each until you find the broken one
- Up to 50 checks

With git bisect:
- Check commit 225 (the middle). Works? Broken?
  → Works → Bug was introduced between 225 and 250
- Check commit 237. Works.
  → Bug is between 237 and 250
- Check commit 243. Broken.
  → Bug is between 237 and 243
- Check commit 240. Works.
  → Bug is between 240 and 243
- Check commit 241. Broken.
  → Commit 241 introduced the bug

5 checks instead of 50.

Using git bisect in practice:

1. Start bisecting
   - Mark the last known good commit
   - Mark the current broken commit

2. Git checks out the midpoint automatically

3. You test: does the bug exist in this version?
   - Yes → mark as "bad"
   - No → mark as "good"

4. Git checks out the next midpoint

5. Repeat until the exact breaking commit is found

This works even with hundreds or thousands of commits
between the good and bad versions.

Binary Search Debugging

When a piece of code produces wrong output but you do not know where the error is, apply bisection to the code itself.

Your program has 200 lines and produces the wrong result.

Strategy:
1. Add a check at the midpoint (line 100)
   - Print the value of key variables at line 100
   - Are they correct at this point?

2. If correct at line 100:
   - The bug is between line 100 and line 200
   - Check line 150 next

3. If incorrect at line 100:
   - The bug is between line 1 and line 100
   - Check line 50 next

4. Continue halving until you find the exact line
   where values go from correct to incorrect

In 8 steps, you can narrow 200 lines to a single line.

Commenting Out Code Sections

A variation of elimination: remove half the code and see if the problem persists.

Scenario: Your web page layout is broken.
You have 10 CSS files loaded.

Step 1: Comment out files 6-10
- Page still broken? → Problem is in files 1-5
- Page fixed? → Problem is in files 6-10

Step 2: If problem is in files 1-5, comment out files 3-5
- Page still broken? → Problem is in files 1-2
- Page fixed? → Problem is in files 3-5

Step 3: Continue until you find the exact file

Step 4: Within that file, apply the same technique
- Comment out the bottom half of the rules
- Narrow down to the exact CSS rule causing the issue

This also works for:
- JavaScript modules
- Configuration settings
- Feature flags
- Database migrations

Toggling Feature Flags

Modern software often uses feature flags to enable or disable features independently.

Problem: The application is crashing intermittently
since last week's deployment, which included 6 new features.

One-by-one approach:
- Disable feature 1. Still crashing? Yes.
- Disable feature 2. Still crashing? Yes.
- Disable feature 3. Still crashing? Yes.
- Disable feature 4. Still crashing? No.
- Feature 4 was the problem.
- Worst case: 6 toggles.

Bisection approach:
- Disable features 4, 5, 6. Still crashing?
  → No → Problem is in features 4, 5, or 6
- Re-enable 5 and 6, keep 4 disabled. Still crashing?
  → No → Feature 4 is the problem
- 2 toggles instead of up to 6

With 20 features, bisection finds the problem in
about 5 toggles instead of up to 20.

Network Troubleshooting

Problem: Cannot reach a web server at example.com

The path: Your computer → Router → ISP → Internet → Server

Bisection:
1. Can you reach your router? (ping 192.168.1.1)
   → Yes → Problem is beyond your router
2. Can you reach your ISP's DNS? (ping 8.8.8.8)
   → Yes → Problem is beyond your ISP's basic connectivity
3. Can you resolve the domain? (nslookup example.com)
   → No → DNS problem
   → Yes → The server itself may be down

Each step cuts the network path in half,
quickly isolating where the connection fails.

When Bisection Does Not Work

Bisection requires certain conditions:

Bisection works when:
- The problem is monotonic (once it breaks, it stays broken)
- You can test any midpoint
- The problem has a single cause

Bisection struggles when:
- Multiple things broke at the same time
  (two bugs introduced in different commits)
- The problem is intermittent
  (works at the midpoint sometimes, not others)
- You cannot easily test a midpoint
  (cannot build from an arbitrary old commit)

Workarounds:
- For multiple causes: Find and fix one, then bisect again
  for the remaining issue
- For intermittent bugs: Run each midpoint test multiple
  times to increase confidence
- For untestable midpoints: Skip that midpoint, try
  a nearby one instead

Common Pitfalls

  • Checking things one at a time when bisection is possible. Linear search through a long list of possibilities is slow. Always ask: "Can I split this in half?"
  • Forgetting to verify your test is reliable. If your test for "is the bug present?" gives wrong answers, bisection will lead you to the wrong commit or line.
  • Not defining "good" and "bad" clearly. You need a clear, repeatable way to determine if the problem exists at any given point. Vague criteria waste time.
  • Giving up when the first bisection is unclear. Sometimes the midpoint test is ambiguous. Try a nearby point instead of abandoning the approach entirely.
  • Applying bisection to non-monotonic problems without realizing it. If the bug appears, disappears, and reappears across the history, simple bisection will not find it. You need a different approach.
  • Changing the test conditions between steps. Each test must be done under the same conditions. If you change the test data or environment between steps, you are not actually eliminating possibilities.

Key Takeaways

  • Bisection finds a problem in a large space by cutting the possibilities in half with each test.
  • For N items, bisection takes about log2(N) steps. That is 10 steps for 1,000 items, or 20 steps for a million.
  • Git bisect applies this technique to find the exact commit that introduced a bug.
  • Commenting out code, toggling feature flags, and network path testing are all forms of elimination by halving.
  • Bisection requires a reliable test and a monotonic problem (once broken, stays broken).
  • When something breaks and the cause is not obvious, your first question should be: "Can I split the problem space in half?"