easyBinary SearchPure DSA~15 min
First Failing Build
A CI pipeline produced builds numbered 1..n. At some point a regression was introduced, and every build from that point onward fails. You can call isBad(build) to test any build. Find the first failing build with as few checks as possible.
Problem
Builds 1..n are 'good' then 'bad' (monotonic: once bad, always bad). Given n and an oracle isBad(x), return the smallest x for which isBad(x) is true. It is guaranteed at least one build is bad.
Input
An integer n (1 ≤ n ≤ 2^31 − 1) and a predicate isBad(x) returning a boolean.
Output
The smallest build number x with isBad(x) == true.
Constraints
- 1 ≤ n ≤ 2,147,483,647
- isBad is monotonic: false...false,true...true
- At least one build is bad
- Minimise the number of isBad calls (O(log n))
Examples
Example 1
Input
n = 5, bad builds = {4, 5}Output
4
isBad(1..3) are false, isBad(4) and isBad(5) are true. The first true is build 4.
Example 2
Input
n = 1, bad builds = {1}Output
1
Only one build and it is bad.