blob: 4b87ee6e9656a7fb54775af097a0b8aa5c632997 (
plain)
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
|
// 278. First Bad Version
#include "leetcode.h"
/*
* 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 minimise the number of calls to the api.
*/
bool isBadVersion(int version);
int firstBadVersion(int n) {
int start = 0, end = n;
while (end - start > 1) {
int mid = start + (end - start) / 2;
if (isBadVersion(mid))
end = mid;
else
start = mid;
}
return end;
}
int main() {
printf("%d\n", firstBadVersion(5)); // expect: 4
printf("%d\n", firstBadVersion(1)); // expect: 1
}
|