[C++] LeetCode (릿코드) 278 : First Bad Version

문제

First Bad Version - LeetCode

First Bad Version - LeetCode

코드

class Solution
{
    public:
        int search(vector<int> &nums, int target)
        {
            int lo = 0;
            int hi = nums.size() - 1;
            
            while (lo <= hi)
            {
                int md = (lo + hi) / 2;
                if (nums[md] == target)
                {
                    return md;
                }
                
                if (nums[md] < target)
                {
                    lo = md + 1;
                }
                else
                {
                    hi = md - 1;
                }
            }
            return -1;
        }
};

설명

isBadVersion() API를 통해 해당 버전이 bad version인지 확인할 수 있다.
한번 bad version이 된 이후의 version은 모두 bad version이다.
이 때, 최초의 bad version을 찾는 문제이다.version을 배열로 표현하면 { good, good, good, ..., bad, bad, bad } 의 형태일 것이다.
즉, 정렬된 상태이기 때문에 이분탐색을 사용할 수 있다.
good version일 경우 그 버전 이하의 버전은 모두 good version이기 때문에 탐색할 필요가 없다.
bad version일 경우 res에 저장한다. 그 버전 이후의 버전은 최초의 bad version일 가능성이 없기 때문에 배제한다.
탐색을 반복할 때 나오는 bad version은 모두 res에 저장된 값보다 이른 값이므로 갱신한다.n의 최댓값은 2^31-1 이기 때문에 중간값을 (lo + hi) / 2 로 구하면 오버플로우가 일어난다.
따라서 lo + (hi - lo) / 2 로 구하거나 long long int 자료형을 사용하여야 한다.