[leetCode][알고리즘] 278. First Bad Version

문제 설명

LeetCode
278. First Bad Version

PM이 되어 첫 Bad Version을 찾아라. 불량 이후에 출시된 버전들은 모두 Bad로 체크된다.

버전의 개수와 Bad Version임을 알려주는 API(함수)가 주어질 때, 최초 Bad Version 인덱스를 출력하라.

 

제한사항

• 1 <= bad <= n <= 231 - 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.

Input: n = 1, bad = 1
Output: 1

문제 풀이

이진탐색으로 찾으면 된다. (BinarySearch)

응용해서 우리는 isBadVersion(version) 기준으로 체크하면 된다.

문제의 배열은 1부터 시작하나, 우리는 0부터 체크하는 것만 유의하자.

1. left = 0, right = n-1 시작, 중간지점(i)설정
2. isBadVersion(version) 이 false면 해당 지점 이후로 탐색 👉 left=i+1
3. isBadVersion(version) 이 true면 min 체크, 해당 지점 이전 탐색 👉 right=i-1

Code

var solution = function(isBadVersion) {
    return function(n) {
        let min = n
        let left = 0, right = n-1
        
        while(left <= right) {
            const i = left + Math.floor((right - left) / 2)
        
            if (isBadVersion(i+1)) {
                min = Math.min(min, i)
                right = i-1
            } else left = i+1
        }
        return min + 1
    };
};

결과