[LeetCode] First Bad Version - 자바스크립트 풀이

문제 링크

왜 "Advanced" Binary Search 인지 모르겠으나 여기서 원하는 대로 풀어드림.

 

1. 접근 방법

 

(1) 장애 난 버전이랑 그렇지 않은 버전을 나누어서 탐색하면 되므로 이진탐색으로 접근한다

 

(2) 이전 버전 mid - 1이 정상 버전이고 지금 검사중인 mid 버전이 장애 난 버전이면 지금 검사중인 mid 버전 리턴.

if (!isBadVersion(mid - 1) && isBadVersion(mid)) return mid;

 

(3) 그 외 경우에서, 지금 버전 mid가 장애 난 버전이면 왼쪽 리스트 탐색하고, 정상 버전이면 오른쪽 리스트를 탐색한다.

if (isBadVersion(mid)) {
  right = mid;
} else {
  left = mid + 1;
}

 

(4) left 리턴

 

2. 전체 풀이

 

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