278 First Bad Version

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)

275 H-Index II

287 Find the Duplicate Number

Last modified 2yr ago

Copy link

Contents

278. First Bad Version

1. Question

2. Implementation

3. Time & Space Complexity

278. First Bad Version​

1. Question

2. Implementation

3. Time & Space Complexity

278. First Bad Version