Description
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.
Examples:
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Example 2:
Input: n = 1, bad = 1
Output: 1Solution in Python
Python
class Solution:
def firstBadVersion(self, n: int) -> int:
left, right = 1, n # Initialize the search range from 1 to n
# Perform binary search
while left < right:
mid = left + (right - left) // 2 # Calculate the middle version to avoid overflow
# Call the API to check if the middle version is bad
if isBadVersion(mid):
# If mid is bad, then the first bad version is either mid or before it
right = mid # Narrow down to the left half including mid
else:
# If mid is not bad, the first bad version must be after mid
left = mid + 1 # Narrow down to the right half excluding mid
# At the end of the loop, left == right, pointing to the first bad version
return leftExplanation of the Code:
- Initialization:
- The function takes
nas the input, which represents the total number of versions. - We initialize two pointers,
leftandright.leftstarts at1(the first version), andrightstarts atn(the last version).
- The function takes
- Binary Search Loop:
- The loop runs while
leftis less thanright. - In each iteration, we calculate the middle version
midasleft + (right - left) // 2. This avoids potential integer overflow that could occur with large values ofnwhen using(left + right) // 2. - We use the API
isBadVersion(mid)to check whether the middle version is bad:- If
isBadVersion(mid)returnsTrue, it means the first bad version must be atmidor earlier, so we moverighttomid. - If
isBadVersion(mid)returnsFalse, it means the first bad version is aftermid, so we movelefttomid + 1.
- If
- The loop runs while
- Return the First Bad Version:
- The loop terminates when
leftequalsright. At this point, bothleftandrightpoint to the first bad version, so we returnleft.
- The loop terminates when
Solution in C++
C++
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n; // Initialize the search boundaries from 1 to n
// Perform binary search
while (left < right) {
int mid = left + (right - left) / 2; // Calculate the middle version to prevent overflow
// Use the API to check if mid is a bad version
if (isBadVersion(mid)) {
// If mid is bad, the first bad version could be mid or before it
right = mid; // Narrow down the search to the left side including mid
} else {
// If mid is not bad, the first bad version must be after mid
left = mid + 1; // Narrow down the search to the right side, excluding mid
}
}
// When the loop ends, left == right, pointing to the first bad version
return left;
}
};Solution in Javascript
JavaScript
var solution = function(isBadVersion) {
/**
* @param {integer} n - Total versions
* @return {integer} - The first bad version
*/
return function(n) {
let left = 1; // Start of the search range (first version)
let right = n; // End of the search range (last version)
// Binary search to find the first bad version
while (left < right) {
let mid = Math.floor(left + (right - left) / 2); // Find the middle point to prevent overflow
// Check if mid is a bad version
if (isBadVersion(mid)) {
// If mid is a bad version, the first bad version is at mid or before
right = mid; // Narrow the search to the left half (including mid)
} else {
// If mid is not a bad version, the first bad version must be after mid
left = mid + 1; // Narrow the search to the right half (excluding mid)
}
}
// At the end of the loop, left == right and both point to the first bad version
return left;
};
};Solution in Java
Java
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1; // Start of the search range (first version)
int right = n; // End of the search range (last version)
// Perform binary search to find the first bad version
while (left < right) {
int mid = left + (right - left) / 2; // Calculate the middle point to avoid overflow
// Check if mid is a bad version using the provided isBadVersion API
if (isBadVersion(mid)) {
// If mid is bad, the first bad version could be at mid or earlier
right = mid; // Narrow down the search to the left half (including mid)
} else {
// If mid is not bad, the first bad version must be after mid
left = mid + 1; // Narrow down the search to the right half (excluding mid)
}
}
// After the loop, left will equal right and point to the first bad version
return left;
}
}