278. First Bad Version 풀이 - js

해당 포스팅은 릿코드 278번 First Bad Version 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 이진탐색 문제이다.

문제

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.

input으로 버전 수인 n이 주어진다.
버전에서 isBadVersion이 false이면 good 버전, true이면 bad 버전이다.
한 버전에서 bad 버전일 시 그 다음 버전들은 전부 bad 버전이다.

첫 bad 버전을 찾아서 리턴하라.

풀이

한 버전에서 bad 버전일 시 그 다음 버전들이 전부 bad 버전이다.
첫 bad 버전을 찾으려면 이진탐색을 이용해 계속 반복문 돌리다가 반복문을 탈출하면 end를 리턴하면 된다.

반복문 탈출 조건은 start >= end이다.

while(start < end) {
  let mid = Math.floor((start+end) /2);
  let test = isBadVersion(mid);
  test === false ? start = mid + 1 : end = mid;
}

이진탐색을 통해 start와 end의 idx를 첫 bad 버전을 찾는 방향으로 조정한다.
반복문을 탈출하게 되면 start는 마지막 good 버전, end는 첫 bad 버전이게 된다.
따라서 end를 리턴하면 된다.

전체 코드

/**
 * 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 start = 0;
        let end = n;
        while(start < end) {
            let mid = Math.floor((start+end) /2);
            let test = isBadVersion(mid);
            test === false ? start = mid + 1 : end = mid;
        }
        return end;
    };
};