Minimum Tests to Find the Broken Revision
You have 100 sequential code revisions. At some point, a bug was introduced -- meaning revisions $1$ through $k-1$ are clean, and revisions $k$ through $100$ are broken. You can test any revision to determine whether it is clean or broken.
What is the minimum number of tests needed to guarantee you find the exact revision $k$ that introduced the bug?
Hints
- Think about how much information each test gives you -- it splits the candidate set into two groups.
- Binary search halves the search space each time. How many halvings reduce 100 to 1?
- Compute $\lceil \log_2(100) \rceil$. Since $2^6 = 64 < 100 \leq 128 = 2^7$, you need 7 tests.
Worked Solution
How to Think About It: This is a classic binary search setup. Each test tells you whether the bug was introduced before or after a given revision, which splits the remaining candidates roughly in half. The question is really asking: how many times can you halve 100 before you get down to 1 candidate?
Quick Estimate: $2^6 = 64$ and $2^7 = 128$. Since $64 < 100 < 128$, six tests are not enough to distinguish 100 candidates, but seven are. So the answer is 7.
Approach: Use binary search. Each test on a midpoint revision partitions the remaining candidates into two halves.
Formal Solution:
Maintain a search interval $[\text{low}, \text{high}]$ initialized to $[1, 100]$.
- Test the midpoint $\text{mid} = \lfloor (\text{low} + \text{high}) / 2 \rfloor$.
- If $\text{mid}$ is broken, the bug was introduced at or before $\text{mid}$, so set $\text{high} = \text{mid}$.
- If $\text{mid}$ is clean, the bug was introduced after $\text{mid}$, so set $\text{low} = \text{mid} + 1$.
- Repeat until $\text{low} = \text{high}$.
The number of tests needed is the number of halvings required to reduce 100 candidates to 1:
$$\lceil \log_2(100) \rceil = \lceil 6.644 \rceil = 7$$
To verify, trace through the candidate count after each test:
- Start: 100 candidates
- After test 1: 50
- After test 2: 25
- After test 3: 13
- After test 4: 7
- After test 5: 4
- After test 6: 2
- After test 7: 1 (found!)
This is exactly the algorithm behind git bisect, which binary-searches through commits to find the one that introduced a bug.
Answer: The minimum number of tests is $\lceil \log_2(100) \rceil = 7$.
Intuition
This is the most fundamental information-theoretic argument in computer science: if you have $N$ possibilities and each test gives a binary (yes/no) answer, you need at least $\lceil \log_2 N \rceil$ tests. Each test carries at most 1 bit of information, and you need $\log_2 N$ bits to specify which of the $N$ candidates is the answer.
In practice, this is exactly how git bisect works -- you tell it a known-good commit and a known-bad commit, and it binary-searches through the history to find the first broken commit in $O(\log n)$ tests. The same logic applies to any monotone search: if you know the answer changes from "no" to "yes" at some unknown point in a sorted sequence, binary search finds that threshold optimally.