First Bad Version
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.
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 search problem on a monotonic structure. All good versions come before all bad versions, so there is a single partition point to locate.
Key Constraints:
1 <= bad <= n <= 2^31 - 1, so n can be up to about 2.1 billion. A linear scan would make up to 2.1 billion API calls, which is too slow. The solution must be logarithmic.1 <= badguarantees at least one bad version, so we never have to handle the case where no bad version exists.- The 2^31 - 1 bound also forces care with the midpoint calculation. Computing
(low + high) / 2adds two values that can each approach 2^31 - 1, and their sum overflows a signed 32-bit integer. The approaches below compute the midpoint aslow + (high - low) / 2to stay within range.
Approach 1: Linear Scan
Intuition
Start from version 1 and check each version in order. The first version where isBadVersion returns true is the answer. Test version 1; if it is good, move to version 2, and continue until the first bad version appears. The approach is correct but ignores the monotonic structure: each call rules out only the single version it tested.
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 eliminates only a single version. Because the versions are partitioned into a good block followed by a bad block, we can eliminate half the remaining range with each call instead.
Approach 2: Binary Search
Intuition
The versions form a monotonic sequence: all good versions come first, then all bad versions. That monotonicity is what binary search needs. Instead of checking versions one at a time, we check the middle version and discard half the range based on the result.
If the middle version is bad, the first bad version is at the middle or before it. If the middle version is good, the first bad version is after the middle. Either way, the search range halves with each API call, so for n = 2^31 - 1 the count drops from about 2 billion to at most 31, since log2(2^31) = 31.
The loop maintains one invariant: the first bad version always lies within [low, high]. When mid is bad, we set high = mid rather than mid - 1 because mid itself might be the first bad version, and dropping it could discard the answer. When mid is good, every version up to and including mid is good, so we set low = mid + 1. Each step shrinks the range while keeping the answer inside it, and the range never becomes empty because mid is strictly less than high whenever low < high. When low == high the range holds exactly one version, which is the first bad one.
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.
Binary search always searches the full range [1, n], so it costs about log2(n) calls regardless of where the first bad version sits. When the first bad version is near the start, we can do fewer calls by finding a tight upper bound before searching.
Approach 3: Exponential (Galloping) Search
Intuition
If the first bad version is small (say version 3 out of a billion), binary search still starts at the midpoint near 500 million and spends several calls walking back down. We can instead expand a bound from the left: check version 1, then 2, then 4, 8, 16, and so on, doubling each time until a call returns bad. Once a bad version is found at bound, the first bad version lies between the previous bound and bound, and we binary search that narrow window.
The doubling phase takes about log2(p) calls to bracket the first bad version at position p, and the binary search over the bracketed window takes another log2(p) calls, since the window has size at most p. The total is O(log p), which beats O(log n) whenever the first bad version is far from the end.
Algorithm
- Set
bound = 1. - While
bound < nandisBadVersion(bound)isfalse, doublebound(capping it atn). - Now the first bad version lies in
[bound / 2 + 1, bound]: everything atbound / 2and below was good, andboundis bad (or equalsn). Setlow = bound / 2 + 1andhigh = min(bound, n). - Binary search this window exactly as in Approach 2: while
low < high, computemid = low + (high - low) / 2, sethigh = midifmidis bad, elselow = mid + 1. - Return
low.
Example Walkthrough
Code
- Time Complexity: O(log p), where p is the position of the first bad version. The doubling phase takes about log2(p) calls, and the binary search over the bracketed window of size at most p takes another log2(p) calls. This is O(log n) in the worst case (bad version near the end) but faster when the bad version is near the start.
- Space Complexity: O(1). We track
bound,low,high, andmid.
For this problem the input range [1, n] is fully known up front, so plain binary search (Approach 2) is the standard choice and its 31-call worst case is already small. Exponential search matters when the upper bound is unknown or unbounded, such as searching a stream or an infinite sorted sequence, where you cannot start binary search without first bracketing the target.