Quiz
Warm-up from lesson 7-2: while minimizing a failing input you cut it in half and test each half. Both halves pass on their own. What did you still learn?
Bisection: the logarithm on your side
The halving trick from lesson 7-2 generalizes into the most powerful search move in debugging: bisection. Whenever a bug hides somewhere in an ordered range, test the midpoint and throw away the half that cannot contain it.
One quick definition before the best example. Professional teams keep code in version control — a tool that records a snapshot of the whole project every time someone finishes a change. Each recorded snapshot is called a commit, the standard tool is Git, and you can check out (reload) any old commit to run the project exactly as it was at that moment. Git gets its own course later; what matters here is that commits form an ordered timeline, and ordered is all bisection needs.
- history: it worked last month, 1,000 commits ago. Check out the middle commit, run the failing test, and 1,000 suspects become 500, then 250...
- code: comment out or bypass half a pipeline to learn which half hides the fault
- input: exactly what you did to the median list
Each test halves the suspects, so n suspects need only log₂(n) tests: 1,024 commits fall in 10 checks, a million in 20. Git automates the history version as git bisect: you mark one commit good and one bad, Git checks out midpoints, and you answer good or bad until it names the first bad commit.
Code exercise · python
Run a simulated git bisect. Commits 1 to 16, commit 1 known good, 16 known bad. is_broken plays the role of running your test at a checked-out commit. Watch four questions find the exact first bad commit.
Code exercise · python
Your turn. Same bisection, bigger haystack: 1,024 commits, bug somewhere unknown (is_broken knows). Write the loop from the example, also counting the steps, and print the two lines shown. Predict the step count with log₂ before you run.
Quiz
Your team has a regression somewhere in the last 1,000,000 commits (a monorepo — a single repository holding all of a company's code — really can accumulate that many). Roughly how many bisection steps find the first bad commit?