diff options
Diffstat (limited to 'first_bad_version.c')
-rw-r--r-- | first_bad_version.c | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/first_bad_version.c b/first_bad_version.c new file mode 100644 index 0000000..4b87ee6 --- /dev/null +++ b/first_bad_version.c @@ -0,0 +1,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 +} |