(Leet Code c++)First Bad Version

278. First Bad Version

 

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 <= 231 - 1

이분 탐색을 통한 문제 풀이.

n의 범위가 INT_MAX 정도의 값이다.

그렇기 때문에 중간값 mid를 구하기 위해서 front와 back이 필요한데, int형이 아닌 long long형으로 선언을 했다.

(front + back의 결과가 int형의 범위를 벗어날 수 있기 때문에)

 

이 두 변수를 이용해 이분 탐색을 진행.

중간값 mid로 isBadVersion(mid)를 실행한다.

 

이 결과가 false라면 bad version이 아니기 때문에 front 범위를 늘려주도록 한다.

 

만약 결과가 true라면 bad version에 속하기 때문에, 최소 bad version을 찾아야 한다.

그렇기 때문에 back 값을 줄여 다시 찾아야 한다.

 

이분 탐색이기 때문에 front를 결과로 리턴하면 된다.

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

class Solution {
public:
    int firstBadVersion(int n) {
        long long front = 0, back = n;
        
        while(front <= back){
            long long mid = (front + back) / 2;
            
            if(!isBadVersion(mid)){
                front = mid + 1;
            }
            else{
                back = mid - 1;
            }
        }
        
        return front;
    }
};