Binary search for the first index where a predicate is true
A release dashboard lists every build of the app, oldest first. A bug appeared at some point and has been present in every build since. Running the end-to-end check on one build takes minutes, so checking them one by one with findIndex is far too slow. Like git bisect, you want the first bad build using as few checks as possible.
Implement bisectFirst(array, predicate), which returns the index of the first element for which predicate returns a truthy value.
bisectFirst(array, predicate) // => number
The array is partitioned by the predicate: it is falsy for every element up to some point and truthy for every element after it. Either part can be empty. Examples: builds before and after a regression, sorted timestamps tested with t >= cutoff, or sorted prices tested with price > budget.
-1 if none does (including an empty array).predicate(element, index, array), like findIndex.predicate at most Math.ceil(Math.log2(array.length + 1)) times. That is 10 calls for 1,000 elements and 20 for a million. An empty array means no calls at all.findIndex, findLastIndex, indexOf or lastIndexOf, and do not mutate array.const builds = [
{ id: 'b101', broken: false },
{ id: 'b102', broken: false },
{ id: 'b103', broken: true },
{ id: 'b104', broken: true },
];
bisectFirst(builds, (build) => build.broken); // => 2
const timestamps = [1000, 1500, 1500, 2200, 3100];
bisectFirst(timestamps, (t) => t >= 1500); // => 1
bisectFirst(timestamps, (t) => t >= 5000); // => -1
bisectFirst(timestamps, (t) => t >= 0); // => 0
bisectFirst([], () => true); // => -1