aboutsummaryrefslogtreecommitdiff
path: root/first_bad_version.c
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
}