First Bad Version

Problem

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 <= $2^{31} - 1$

Solution

• 관리자가 제품의 버전을 관리하며, 한 번 잘못된 버전 이후는 모두 bad 버전이다.
  • ex. 1(good), 2(good), 3(bad), 4(bad), 5(bad), ...
• isBadVersion(version) API를 호출하여 버전상태를 확인할 수 있다.
  • bad or good
• $2^{31} - 1$범위로, long long int 를 선언해서 사용해야 한다.
• Binary Search를 사용하여 low/high의 mid를 탐색하여 bad 버전인지 bool 체크를한다.
• Binary Search를 하는 이유는 시간복잡도가 O(log_n)이 되기 때문이다. 참고로, for문을 사용할 경우에는 시간 복잡도가 O(n)이다.

Code

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
    // long long 또는 unsigned int 사용
    long long low = 0;
    long long high = n;
    long long ans = 0;

    while (low <= high) {
        long long  mid = (high + low) / 2;
        if (isBadVersion(mid)) {
            ans = mid;
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    return ans;
    }
};