-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path278.first-bad-version.cpp
More file actions
57 lines (51 loc) · 1.59 KB
/
278.first-bad-version.cpp
File metadata and controls
57 lines (51 loc) · 1.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Tag: Binary Search, Interactive
// Time: O(logN)
// Space: O(1)
// Ref: -
// Note: Range;
// Video: https://youtu.be/xNzBpfqzYSg
// 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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
//
// Example 1:
//
// Input: n = 5, bad = 4
// Output: 4
// Explanation:
// call isBadVersion(3) -> false
// call isBadVersion(5) -> true
// call isBadVersion(4) -> true
// Then 4 is the first bad version.
//
// Example 2:
//
// Input: n = 1, bad = 1
// Output: 1
//
//
// Constraints:
//
// 1 <= bad <= n <= 231 - 1
//
//
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)){
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};