First Bad Version (opens in a new tab) Easy

Problem

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false

call isBadVersion(5) -> true

call isBadVersion(4) -> true

Then 4 is the first bad version.

Summary

To solve this problem, we can use binary search to efficiently find the first bad version. The binary search algorithm works by repeatedly dividing the search interval in half.

Solution

In TypeScript

// The isBadVersion API is defined in the parent class VersionControl.
// isBadVersion(version: number): boolean {
//     ...;
// };
 
class Solution extends VersionControl {
    firstBadVersion(n: number): number {
        let left = 1;
        let right = n;
 
        while (left < right) {
            const mid = left + Math.floor((right - left) / 2);
 
            if (this.isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
 
        return left;
    }
}

In Python

# The isBadVersion API is defined in the parent class VersionControl.
# def isBadVersion(version: int) -> bool:
#     pass
 
class Solution(VersionControl):
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
 
        while left < right:
            mid = left + (right - left) // 2
 
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
 
        return left

Step-by-step explanation

1. We initialize two pointers, left and right, which represent the boundaries of the search interval. Initially, left is set to 1 (the first version) and right is set to n (the last version).

let left = 1;
let right = n;

2. We run a while loop as long as left is less than right. This loop will continue until we either find the first bad version or exhaust the search interval.

while (left < right) {
		// ...
}

3. Inside the loop, we calculate the middle index mid of the search interval by adding left and half the difference between right and left. This prevents potential integer overflow issues that could arise from simply calculating (left + right) / 2.

const mid = left + Math.floor((right - left) / 2);

4. We check if the version at index mid is a bad version by calling the isBadVersion function. If it is, it means that the first bad version is at mid or to its left. So, we update right to mid.

if (this.isBadVersion(mid)) {
		right = mid;
}

5. If the version at index mid is not a bad version, it means that the first bad version is to the right of mid. So, we update left to mid + 1.

} else {
		left = mid + 1;
}

6. After the loop, left will be pointing to the first bad version, so we return left.

return left;

This binary search algorithm efficiently finds the first bad version by repeatedly reducing the search interval in half until either the first bad version is found or the search interval is exhausted.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(log n), where n is the number of versions. Binary search reduces the search space by half at each iteration, resulting in a logarithmic time complexity.

Space Complexity

The space complexity of this solution is O(1) since we only use a constant amount of additional memory to store the variables left, right, and mid.