Dare2Solve
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 one, all the following versions are also bad. Given an API bool isBadVersion(int version)
, which returns whether a version is bad, your task is to find the first bad version in the sequence of versions.
You need to minimize the number of calls to the isBadVersion
API.
The problem can be reduced to a classic binary search scenario where you are trying to find the first occurrence of a bad version in a sequence. By narrowing down the search space through binary search, we can efficiently find the first bad version with minimal API calls.
The idea is to repeatedly divide the search space in half, which allows us to focus only on the relevant portion of the sequence that could contain the first bad version.
left
at 1 (the first version) and right
at n
(the last version).mid
is bad, then the first bad version must be at mid
or before it, so move the right
pointer to mid
.mid
is not bad, then the first bad version must be after mid
, so move the left
pointer to mid + 1
.left
equals right
. At this point, left
will be pointing to the first bad version.O(log n)
. The binary search algorithm reduces the search space by half each time, leading to a logarithmic time complexity relative to the number of versions n
.
O(1)
. The algorithm only uses a constant amount of extra space for the pointers and midpoint calculation.
// Forward declaration of isBadVersion API.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = (left + right) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let l = 1, r = n;
while (l < r) {
const mid = Math.floor((l + r) / 2);
if (isBadVersion(mid)) r = mid;
else l = mid + 1;
}
return l;
};
};