First Bad Version
Problem
Given n versions [1, 2, ..., n] and an API isBadVersion(version) that returns whether a version is bad, return the first bad version such that all versions after it are bad.
- 1 ≤ n ≤ 2³¹ - 1
- The isBadVersion API is monotonic: if version x is bad, then all versions > x are bad.
Example
n = 54Versions 1, 2, and 3 are good, while versions 4 and 5 are bad. The algorithm uses binary search to efficiently narrow down the first bad version. Starting with left=1 and right=5, it checks mid=3. Since version 3 is good, it moves left to 4. Then it checks mid=4, which is bad, so it moves right to 4. When left equals right, it returns 4 as the first bad version.
Approach
Straightforward Solution
A naive approach would check each version sequentially from 1 to n, calling isBadVersion until the first bad version is found. This approach is O(n) and inefficient for large n.
Core Observation
The problem reduces to finding the boundary point in a monotonic boolean sequence where values switch from False (good) to True (bad). This boundary search is a classic use case for binary search.
Path to Optimal
Recognizing the monotonic property of isBadVersion, binary search can be applied to find the transition point efficiently. By repeatedly checking the middle version, the search space halves each iteration. If mid is bad, the first bad version lies at mid or to the left; if mid is good, it lies to the right. This logic narrows down the search to O(log n) time.
Optimal Approach
Initialize two pointers, left = 1 and right = n. While left < right, compute mid = (left + right) // 2. If isBadVersion(mid) is True, move right to mid; else move left to mid + 1. When left equals right, return left as the first bad version.
Time
O(log n)
Each iteration halves the search space by moving either left or right pointer, resulting in logarithmic time relative to n.
Space
O(1)
Only a fixed number of variables (left, right, mid) are used, regardless of input size.
Pattern Spotlight
Modified Binary Search (Boundary Search)
When searching for a boundary or transition point in a monotonic predicate over a sorted domain, use binary search to repeatedly halve the search space by testing the midpoint and adjusting boundaries accordingly.
Solution
| 1 | class Solution: |
| 2 | def firstBadVersion(self, n: int) -> int: |
| 3 | |
| 4 | left = 1 |
| 5 | right = n |
| 6 | |
| 7 | while left < right: |
| 8 | |
| 9 | mid = (left + right) // 2 |
| 10 | |
| 11 | if isBadVersion(mid): |
| 12 | right = mid |
| 13 | else: |
| 14 | left = mid + 1 |
| 15 | |
| 16 | return left |
| 1 | public class Solution { |
| 2 | public int firstBadVersion(int n) { |
| 3 | int left = 1; |
| 4 | int right = n; |
| 5 | while (left < right) { |
| 6 | int mid = left + (right - left) / 2; |
| 7 | if (isBadVersion(mid)) { |
| 8 | right = mid; |
| 9 | } else { |
| 10 | left = mid + 1; |
| 11 | } |
| 12 | } |
| 13 | return left; |
| 14 | } |
| 15 | |
| 16 | // The isBadVersion API is defined elsewhere. |
| 17 | boolean isBadVersion(int version) { |
| 18 | // Placeholder for the API. |
| 19 | return false; |
| 20 | } |
| 21 | } |
| 1 | #include <iostream> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | int firstBadVersion(int n) { |
| 8 | int left = 1; |
| 9 | int right = n; |
| 10 | while (left < right) { |
| 11 | int mid = left + (right - left) / 2; |
| 12 | if (isBadVersion(mid)) { |
| 13 | right = mid; |
| 14 | } else { |
| 15 | left = mid + 1; |
| 16 | } |
| 17 | } |
| 18 | return left; |
| 19 | } |
| 20 | |
| 21 | // The isBadVersion API is defined elsewhere. |
| 22 | bool isBadVersion(int version) { |
| 23 | // Placeholder for the API. |
| 24 | return false; |
| 25 | } |
| 26 | }; |
| 1 | var Solution = function() {}; |
| 2 | |
| 3 | Solution.prototype.firstBadVersion = function(n) { |
| 4 | let left = 1; |
| 5 | let right = n; |
| 6 | while (left < right) { |
| 7 | let mid = Math.floor((left + right) / 2); |
| 8 | if (isBadVersion(mid)) { |
| 9 | right = mid; |
| 10 | } else { |
| 11 | left = mid + 1; |
| 12 | } |
| 13 | } |
| 14 | return left; |
| 15 | }; |
| 16 | |
| 17 | // The isBadVersion API is defined elsewhere. |
Step-by-Step Solution
Initialize Search Boundaries to Cover All Versions
| 4 | left = 1 |
| 5 | right = n |
Objective
To set the initial search range covering all versions from 1 to n.
Key Insight
Starting with left at 1 and right at n ensures the entire version range is considered. This setup is essential because the first bad version could be anywhere in this range, and the binary search will progressively narrow it down.
Interview Quick-Check
Core Logic
Setting left = 1 and right = n initializes the binary search boundaries to the full version range.
State & Boundaries
The search space is inclusive of both left and right pointers, ensuring no versions are skipped.
Iteratively Narrow Search Space Using Binary Search
| 7 | while left < right: |
| 9 | mid = (left + right) // 2 |
| 11 | if isBadVersion(mid): |
| 12 | right = mid |
| 13 | else: |
| 14 | left = mid + 1 |
Objective
To repeatedly halve the search space by checking the middle version and adjusting boundaries based on whether it is bad.
Key Insight
By calculating mid as the integer midpoint of left and right, the algorithm tests whether the first bad version lies to the left or right. If mid is bad, the first bad version is at mid or earlier, so right is moved to mid. Otherwise, left is moved to mid + 1. This logic exploits the monotonicity of isBadVersion to discard half the search space each iteration.
Interview Quick-Check
Core Logic
The binary search condition uses isBadVersion(mid) to decide which half of the search space to keep, ensuring the first bad version is never excluded.
State & Boundaries
The loop continues while left < right, stopping when the search space is reduced to a single element.
Common Pitfalls & Bugs
Calculating mid as (left + right) // 2 avoids overflow in languages with fixed integer sizes and ensures correct midpoint.
Return the Identified First Bad Version
| 16 | return left |
Objective
To return the converged pointer as the first bad version after the search space is narrowed to one element.
Key Insight
When left equals right, the search space cannot be reduced further, and this position corresponds to the first bad version. Returning left at this point provides the correct answer.
Interview Quick-Check
Core Logic
Returning left after the loop terminates yields the earliest version that is bad.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
return leftReturn the converged pointer as the first bad version.
When left equals right, the search space is a single version, which must be the first bad version due to the binary search narrowing.
if isBadVersion(mid):Check if the midpoint version is bad using the API.
This check determines which half of the search space contains the first bad version, leveraging the monotonic property of isBadVersion.
right = midMove the right pointer to mid when the midpoint version is bad.
If mid is bad, the first bad version could be mid itself or an earlier version. Moving right to mid keeps mid inside the search space while eliminating later versions.
left = mid + 1Move the left pointer to mid + 1 to search later versions.
If mid is not bad, then mid and all earlier versions are confirmed good. Moving left to mid + 1 discards those versions and continues the search in the later part of the range.
else:Conclude that the search must continue in the right half of the range.
If mid is not bad, this confirms that the first bad version must occur strictly after mid because all earlier versions are guaranteed to be good.
while left < right:Continue binary search while the search interval has more than one candidate.
The loop continues while the search interval contains more than one candidate. Each iteration shrinks the range while maintaining the invariant that the first bad version lies within [left, right].
mid = (left + right) // 2Calculate the midpoint of the current search range.
Computing mid as the integer division of (left + right) // 2 splits the search space evenly, enabling efficient halving each iteration.
left = 1Initialize the left pointer to the first version.
Starting at 1 ensures the search covers all versions from the beginning, as versions are numbered starting at 1.
right = nInitialize the right pointer to the last version.
Setting right to n covers the entire range of versions, ensuring no potential first bad version is excluded.
Test Your Understanding
Why does moving the right pointer to mid when isBadVersion(mid) is True guarantee that the first bad version is not missed?
Because if mid is bad, the first bad version must be at mid or before it, so narrowing the search to [left, mid] preserves the first bad version within the search space.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct First Bad Version from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the First Bad Version drill