[LeetCode] 278. First Bad Version

LeetCode - 278. First Bad Version 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/first-bad-version/

풀이

bool isBadVersion(int version) 함수는 매개변수 version의 상태가 Bad이면 true를 반환하고 그렇지 않으면 false를 반환하는 함수이다.

for-loop에서 초기식 i가 n이하인 경우까지 반복하면서 isBadVersion(i)를 호출한 반환값이 true라면 그 때의 i 값을 반환하는 것으로 해결할 수 있을 것으로 보이지만, n 값의 범위에 의해 $ O(log N) $ 의 시간복잡도로 해결해야 한다.

즉, Binary Search를 통해서 해결해보는 것을 생각할 수 있는데 이때 주의할 점은 mid 값을 구하기 위해 상한과 하한을 더하는 과정에서 int type 오버플로가 발생할 수 있다는 점이다. (=상한과 하한을 더했을 때 int로 표현할 수 있는 최댓값인 $ 2^{31}-1 $ 을 초과할 수 있음)

이와 관련된 좀 더 자세한 내용은 Binary Search를 구현할 때 주의할 점에서 확인할 수 있다.

소스 코드

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

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (isBadVersion(mid)) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};