forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
278-First-Bad-Version.cpp
39 lines (32 loc) · 1.03 KB
/
278-First-Bad-Version.cpp
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
/*
Suppose you have versions and you want to find out the first bad one, which causes all the following ones to be bad.n[1, 2, ..., n]
You are given an API which returns whether is bad. Implement a function to find the first bad version.
Ex.
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
1.- Find the number in the middle of the vector.
2.- Takes a part (first or second), depending on whether or not the target is greater than the middel.
3.- Change the current left or right part.
3.- Do this process until the left reaches the right.
Time: O(log n)
Space: O(1)
*/
class Solution {
public:
int firstBadVersion(int n) {
int left = 1;
int right = n;
while (right > left) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid))
right = mid;
else
left = mid + 1;
}
return left;
}
};