[Leetcode] 278. First Bad Version

#이진탐색

Problem

Leetcode algorithm study plan > 문제 링크

1부터 N까지의 수 중에서 제공되는 isBadVersion 함수를 통해 가장 낮은 수에서의 true값을 찾는 문제. O(log n)으로

isBadVersion 함수

@param {Integer} @return {Boolean} @description 파라메타값으로 넘겨받은 값이 잘못된 버전인지 확인해주는 함수로. 잘못된 버전보다 큰값이 나오면 항상 잘못된 결과를 반납한다.

Solution

O(log n)으로 풀어야하는 문제이므로 이진탐색을 이용한다.

이진탐색 조건중인 배열의 정렬상태를 확인한다.

이진탐색은 배열의 값이 두개가 남았을때 mid는 항상 왼쪽을 바라보게된다는 조건을 이용해서 무한루프가 돌지않게 타겟을 오른쪽인덱스로 맞춰서 조건을 짜면된다

JS Code

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 1, right = n
        
        while(left < right) {
            let mid = Math.floor((left + right) / 2)
            if (!isBadVersion(mid)) left = mid + 1
            else right = mid
        }
        
        return right
    };
};