LeetCode - First Bad Version

문제

귀하는 제품 관리자이며 현재 새로운 제품을 개발하기 위해 팀을 이끌고 있습니다. 유감스럽게도, 당신의 최신 버전은 품질 검사에 실패했습니다. 각 버전은 이전 버전을 기반으로 개발되기 때문에 불량 버전 이후의 모든 버전도 불량 버전입니다.

n개의 버전 [1, 2, ..., n]이 있으며 다음 버전이 모두 불량인 첫 번째 버전을 확인하려고 합니다.

버전이 불량인지 여부를 반환하는 API bool isBadVersion(버전)이 제공됩니다. 함수를 구현하여 첫 번째 불량 버전을 찾습니다. API에 대한 호출 수를 최소화해야 합니다.

Example 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.

Example 2

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

해결

Binary Search로 해결.

• start와 end를 선언한다.
• 중간 값인 mid를 선언한다.
• end가 중간값보다 작으면 end를 mid 왼쪽으로 한칸 옮긴다.
• start가 중간값보다 작으면 start를 mid 오른쪽으로 한칸 옮긴다.
• 이렇게 end나 start값이 변화하면, 자동으로 mid값도 변한다.
• 이후 반복문이 끝나게 되면 start값을 반환한다.

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
      //isBadVersion이 함수이나 인자로 들어옴. 익명함수로 해소
        let start = 1;
        let end = n;
        let mid;
        while (end >= start) {
            mid = Math.floor((start+end)/2);
            if (isBadVersion(mid)) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }
        return start;
    };
};