Problem Statement
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 will return 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.
Solution thought process
If you have to find the first occurrence of an element in a sorted array of some kind, binary search should be the first thing we should be thinking of.
Let's think of the first scenario:
Scenario #1: isBadVersion(mid) => false
1 2 3 4 5 6 7 8 9
G G G G G G B B B G = Good, B = Bad
| | |
left mid right
If we can see that the isBadVersion is returning false for mid, we can adjust our left
to be equal to mid+1
, because we know that we don't have to consider previous [left, mid] region for the answer, as we can see it from the scenario #1.
Scenario #2: isBadVersion(mid) => true
1 2 3 4 5 6 7 8 9
G G G B B B B B B G = Good, B = Bad
| | |
left mid right
If we can see that isBadVersion is returning true for mid, we can adjust our right to be mid-1
and our result = mid
because we have to find the first occurrence of the bad product.
Solution
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
private:
int binarySearch(int t)
{
int L = 1, U = t, result = -1;
while(L<=U)
{
int M = L + (U-L)/2;
bool badVersionResult = isBadVersion(M);
if(badVersionResult == true)
{
result = M;
U = M-1;
}
else {
L = M+1;
}
}
return result;
}
public:
int firstBadVersion(int n) {
return binarySearch(n);
}
};
Complexity
Time complexity: O(logn), on every loop we are making the candidate space into half, giving it a logarithmic complexity.
Space Complexity: O(1), we are not assigning any additional array.
Top comments (0)