visual walkthrough
First Bad Version
Binary search over a boolean predicate, the foundation of search-on-answer.
The idea
The versions look like good, good, good, bad, bad, bad. You want the first bad one with as few isBad calls as possible.
Ask about the middle: a bad answer means the boundary is at or before it; a good answer means it's after.
Complexity
| approach | time | space |
|---|---|---|
| Check every version | O(n) | O(1) |
| Binary search | O(log n) | O(1) |