First Bad Version

The key idea

The versions form a sorted boolean line: a run of false (good) followed by a run of true (bad). The answer is the boundary — the first true. That boundary is monotonic, so binary search finds it in O(log n) calls without scanning every version.

Problem

You are a product manager leading a team that develops a new product. Each version is built on the previous one, so once a version is bad, every version after it is also bad. You are given n versions numbered 1 to n and you want to find the first bad one, which causes all the following ones to be bad. You are given an API isBadVersion(version) that returns whether a given version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Constraints

1 <= bad <= n <= 2^31 - 1

Examples

Input: n = 5, bad = 4 Output: 4

Input: n = 1, bad = 1 Output: 1

Input: n = 8, bad = 6 Output: 6

Complexity

Time: O(log n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →