After a firmware version known to work correctly there are 1,000 commits, and the latest commit has a bug. The bug was introduced by one commit and occurs in every commit after it. When the culprit commit is identified by binary search, as with git bisect, what is the maximum number of times the firmware must be built and tested?

Answer: B. 10

The culprit is one of the 1,000 commits, and each test of the middle commit halves the candidates. Since 2¹⁰ = 1,024 ≥ 1,000, at most 10 tests identify it. Testing one commit at a time from the oldest would take 999 tests in the worst case and about 500 on average, so binary search makes a big difference. To use this method, it is important not to put broken commits on shared branches, so that every commit can be built and tested.

• A. This uses a base-10 logarithm because 1,000 = 10³. Each test only halves the candidates, so the base is 2.
• B. Correct. Since 2¹⁰ = 1,024 ≥ 1,000, 10 tests are enough.
• C. This is close to the average when testing one commit at a time from the oldest; binary search needs far fewer.