278 First Bad Version

1. Question

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 havenversions[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 APIbool isBadVersion(version)which will return whetherversionis bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

2. Implementation

(1) Binary Search
思路:这题是关于git bisect的原理,本质是二分法找左边界问题,注意将数据转换成long类型,避免data overflow
1
/* The isBadVersion API is defined in the parent class VersionControl.
2
boolean isBadVersion(int version); */
3
4
public class Solution extends VersionControl {
5
public int firstBadVersion(int n) {
6
long start = 1, end = n, mid = 0;
7
8
while (start + 1 < end) {
9
mid = start + (end - start) / 2;
10
11
if (!isBadVersion((int)mid)) {
12
start = mid + 1;
13
}
14
else {
15
end = mid;
16
}
17
}
18
return isBadVersion((int)start) ? (int)start : (int)end;
19
}
20
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)