Which commit broke the build
Every commit up to some point built cleanly and every one after it fails. A bisect finds the first bad one without building them all.
- The results are ordered oldest first: a run of passes, then nothing but failures.
- Return the position of the first failure, counting from zero.
- If every commit passed, return -1.
- The very first commit may be the bad one.
first_bad_build(passed: list<bool>) → int
Where you start
def first_bad_build(passed: list[bool]) -> int:
Worked examples
| Call | Result |
|---|---|
first_bad_build([True, True, False, False]) | 2 |
first_bad_build([True, True, True]) | -1 |
first_bad_build([False, False]) | 0 |
first_bad_build([]) | -1 |
Hint
This is what `git bisect` does. Halve the range, and let a failure pull the right edge in while a pass pushes the left edge out.
Reference solution in Python
def first_bad_build(passed: list[bool]) -> int:
lo, hi = 0, len(passed)
while lo < hi:
mid = (lo + hi) // 2
if passed[mid]:
lo = mid + 1
else:
hi = mid
return -1 if lo == len(passed) else lo