LeetCode 278. First Bad Version

題目

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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

翻譯

你是一個產品經理，目前正帶領一個團隊開發新產品，不幸的是，如果有一個新版的產品沒通過測試，在這版本之後全部的新版本都不會通過測試。

假如你有n個版本的產品[1,2, ...,n]，然後你想追蹤是從哪一個版本開始沒通過測試。

這邊有一個 isBadVersion(version) API可以判斷這個版本能不能通過測試。利用這個API實作一個functon來找到第一個壞掉的版本。

範例：
假如目前有5個版本，[1,2,3,4,5]，從第4個版本開始都是壞掉的，一個一個版本丟入API驗證會得到 [true,true,true,false,false]。

思路

1. 最簡單的方法就是跑迴圈，將毎個版本丟入 isBadVersion中判斷，直到發現壞掉的版本，事情沒那麼美好，這種寫法會超過時間無法通過測試，因此需要另外想一個更快的演算法。
2. 以上面n=5，版本4之後就壞掉為例，我們可以把用 isBadVersion之後的版本陣列想像成[1,1,1,0,0]，簡單說就是要找出第一個0出現的位置，其實就是猜數字之類的遊戲
3. 這邊用二分搜尋法來尋找第一個0，一開始最大值max=n，最小值min=1，搜尋的位置為mid = (max+min)/2， 如果 isBadVersion(mid)回傳true，代表壞掉的版本在mid之後，因此min = mid+1，反之亦然，一直搜尋到min>max，mid表示找到第一個壞掉的版本

    example：
    [1,2,3,4,5] --> [1,1,1,0,0]
    max = 5, min = 1   -> mid = 3   isBadVersion(3) = true
    min = mid+1 = 4    -> mid = 4   isBadVersion(4) = false
    max = mid   = 4    -> max > min == false, end loop 

解題

/**
 * 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) {
        var min = 0 ;
        var max = n ;
        var mid;

        // 用二分法進行搜尋，減少loop次數
        while(max > min){
            mid = min+parseInt((max-min)/2); 
            if(isBadVersion(mid)){
                max = mid;
            } else {
                min = mid+1;
            }
        }

        return max;
    };
};

失敗的解法

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {

    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {

        for(var i = 0 ; i <= n ; i++){
            if(isBadVersion(i)){
                return i;
            }
        }
    }
}