[LeetCode] First Bad Version - 이진탐색 (binary search)

문제 

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.

당신은 프로덕트 매니저로서 현재 새로운 상품 개발을 이끌고 있다. 안타깝게도 가장 최근 개발 버전이  품질 테스트를 통과하지 못했다. 모든 버전이 바로 직전 버전을 기반으로 개발되어있기 때문에, 잘못된 버전의 다음 버전 역시 잘못 될 수 밖에 없다. 당신은 총 n개의 버전을 가지고있으며, 문제가 되는 첫 번째 버전을 찾고자한다. 버전이 나쁜지 여부를 boolean 형태로 판단하는 API  isBadVersion(version)를 이용하여 첫 번째 불량 버전을 찾는 함수를 구현하라. 단,  API 호출 횟수를 최소화 할 것.

풀이 

불량버전을 찾는 방법을 최소화하기 위해, 배열의 끝에서부터 불량 여부를 판독하기로 했다. 

var solution = function(isBadVersion) {
/**
 * @param {integer} n Total versions
 * @return {integer} The first bad version
 */
return function(n) {
    for (let i = n; i > 0; i--) {
        if (isBadVersion(i) && !isBadVersion(i-1)) 
           return i;                 
    };
  };
};

Runtime: 6688 ms

Memory Usage: 41.9 MB

잘못된 답은 아닌데. 결과가 다소 충격적. 뒤에서부터 돌아도 비효율적이구나.

 

다른 풀이 1

ChatGPT에게 물어보니 이 문제는 이진탐색(Binary searh)로 접근해야한다고 한다. 

이진탐색(binary search)

: 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 

 

배열 [3, 4, 5, 6, 7, 8, 9]을 이진 탐색 하여 4를 찾는다고 가정하자.

0. 우선 Left와 Right 두 pointer를 설정한다.

1. Left는 배열의 가장 첫번째 값인 3. Right는 가장 마지막 숫자인 9

 

출처 : https://www.programiz.com/dsa/binary-search#google_vignette

2. 중간 값을 찾는다.  Math.floor((right - left) / 2)

3. 찾는 값이 배열의 중간값인지 확인한다. 

4. pointer를 옮겨서 다시 중간값과 비교한다. 

 

위 방법을 이번 문제에 적용해보면 다음과 같다. 

/**
 * @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;
        let right = n;

        while (left < right) {
            const mid = left + Math.floor((right - left) / 2);
            if (isBadVersion(mid)) {
            	// mid가 잘못된 버전이라면, 
                // 이후 버전들도 문제가 있다는 의미기 때문에 right pointer를 mid 위치로 변경한다
                right = mid;
            } else {
                left = mid + 1;
            }
        }
         return left;
    };
};

위 방법으로 풀면 API 호출을 최소화 할 수 있고. 좁은 범위에서 값을 찾을 수 있다. 시간 복잡도는 O(log n)으로 매우 효율적인 알고리즘!