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.
firstBadBuild(passed: list<bool>) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func firstBadBuild(passed []bool) int {
}Worked examples
| Call | Result |
|---|---|
firstBadBuild([]bool{true, true, false, false}) | 2 |
firstBadBuild([]bool{true, true, true}) | -1 |
firstBadBuild([]bool{false, false}) | 0 |
firstBadBuild([]bool{}) | -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 Go
func firstBadBuild(passed []bool) int {
lo, hi := 0, len(passed)
for lo < hi {
mid := (lo + hi) / 2
if passed[mid] {
lo = mid + 1
} else {
hi = mid
}
}
if lo == len(passed) {
return -1
}
return lo
}