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.

The version list should looks like this: good_version1, good_version2, … , bad_version1, bad_version2, …, the bad versions are following the good versions, what you need to do is to find the first bad version. You can think it as to find the first 1 in a 0,1 sequence in which all zeros are all before ones.

The most intuitive way is to iterate the version list from the beginning, and find the first bad version, but this way needs O(n) complexity. A better way to find a specified item in a sorted list is using binary search, this way is also suitable for this problem. But the binary search here needs a little change, since we search for the first item with specified value, the first bad version.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */

public class FirstBadVersion extends VersionControl {
public int firstBadVersion(int n) {
int low = 1;
int hi = n;
while (low < hi) {
int mid = low + (hi - low) / 2;
if (isBadVersion(mid)) hi = mid;
else low = mid + 1;
}
return hi;
}
}

The complexity: O(lgn) / O(1)