First Bad Version
Easy · Binary Search · Binary Search · Interactive
Problem
A product has versions 1, 2, ..., n. One version was built badly, and since each version is built on the one before it, every version after a bad one is bad too.
You cannot see which version that is. You can call isBadVersion(version), which returns true when version is bad. Implement firstBadVersion(n) so that it returns the first bad version, calling the API as few times as you can.
In the examples, bad is the hidden first bad version that the API answers for. Your function does not receive it.
Examples
Input: n = 8, bad = 6 Output: 6
Versions 1 to 5 report good and 6 to 8 report bad, so 6 is the first bad one. Binary search finds it in 3 calls: 4 (good), 6 (bad), 5 (good).
Input: n = 3, bad = 1 Output: 1
Every version is bad, so the answer is the very first one.
Input: n = 5, bad = 5 Output: 5
Only the last version is bad.
Constraints
- 1 <= bad <= n <= 2^31 - 1
Approaches
- Check every version in order — time O(n), space O(1)
Follow-up
What if you are not told n? Probe versions 1, 2, 4, 8, ... until one is bad, then binary search between the last good probe and it. That is exponential (galloping) search, and it takes about 2 · log2(bad) calls, so it is fast whenever the first bad version is early.
Related problems
Start free on Cariara · Coding problems · System design studio
