Problems › JavaScript › patterns
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
Where you start
function firstBadBuild(passed) {
}Worked examples
| Call | Result |
|---|---|
firstBadBuild([true,true,false,false]) | 2 |
firstBadBuild([true,true,true]) | -1 |
firstBadBuild([false,false]) | 0 |
firstBadBuild([]) | -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 JavaScript
function firstBadBuild(passed) {
let lo = 0;
let hi = passed.length;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (passed[mid]) lo = mid + 1;
else hi = mid;
}
return lo === passed.length ? -1 : lo;
}