First Bad Version
Last Updated: March 29, 2026
Understanding the Problem
We have a linear sequence of versions numbered 1 through n. At some point, a version goes bad, and every version after it is also bad. So the sequence looks like: [good, good, ..., good, bad, bad, ..., bad]. We need to find the boundary, the first version where it flips from good to bad.
The catch is that we can only determine whether a version is bad by calling the isBadVersion API, and we want to minimize the number of calls. This is a classic search problem on a sorted (monotonic) structure. The "sorted" property here is that all good versions come before all bad versions, so there's a clean partition point.
Key Constraints:
1 <= bad <= n <= 2^31 - 1-> n can be up to about 2.1 billion. A linear scan would make up to 2.1 billion API calls, which is far too slow. We need something logarithmic.1 <= bad-> There's always at least one bad version. We don't need to handle the "no bad version exists" case.- Given n up to 2^31 - 1, we need O(log n) or better. Binary search fits perfectly: log2(2^31) = 31 calls at most.
Approach 1: Linear Scan
Intuition
The simplest approach: start from version 1 and check each version one by one. The first version where isBadVersion returns true is our answer.
This is what you'd do if you were manually testing versions in order. Start with version 1, test it. Not bad? Move to version 2. Keep going until you hit the first bad one. It's correct, straightforward, and requires zero cleverness. But it completely ignores the structure of the problem.
Algorithm
- Start from version 1.
- For each version
ifrom 1 to n, callisBadVersion(i). - Return the first
iwhereisBadVersion(i)returnstrue.
Example Walkthrough
Code
- Time Complexity: O(n). In the worst case, the bad version is the very last one, so we call
isBadVersionn times. - Space Complexity: O(1). We only use a single loop variable.
Each API call only eliminates a single version. Since the versions are partitioned into a good block followed by a bad block, we can do much better by eliminating half the search space with each call.
Approach 2: Binary Search
Intuition
The versions form a monotonic sequence: all good versions come first, then all bad versions. This is exactly the pattern where binary search shines. Instead of checking versions one at a time, we can check the middle version and immediately eliminate half the search space.
If the middle version is bad, the first bad version is somewhere at or before the middle. If the middle version is good, the first bad version must be after the middle. Either way, we cut the search space in half with each API call. This means we go from potentially 2 billion calls down to at most 31, since log2(2^31) = 31.
The key invariant maintained throughout the binary search is: the first bad version is always within the range [low, high]. When we find that mid is bad, we set high = mid (not mid - 1) because mid itself could be the first bad version. When we find that mid is good, we set low = mid + 1 because the first bad version must come after mid. Each iteration halves the search space, and eventually low and high converge to the same value, which must be the first bad version.
Algorithm
- Set
low = 1andhigh = n. - While
low < high: - Compute
mid = low + (high - low) / 2(to avoid integer overflow). - If
isBadVersion(mid)istrue, sethigh = mid(the first bad version is at mid or earlier). - If
isBadVersion(mid)isfalse, setlow = mid + 1(the first bad version is after mid). - When
low == high, returnlow. This is the first bad version.
Example Walkthrough
Code
- Time Complexity: O(log n). Each API call halves the search space. For n = 2^31 - 1, that's at most 31 calls.
- Space Complexity: O(1). We only use three variables:
low,high, andmid.