第一個錯誤的版本（easy）

更好的閱讀體驗應該是：

審題-思考
答題
整理-歸納

一、題目

LeetCode：278.第一個錯誤的版本

你是產品經理，目前正在帶領一個團隊開發新的產品，不幸的是，你的產品的最新版本沒有通過質量檢測，由于每個版本都是基于之前的版本開發的，所以錯誤的版本之后的所有版本都是錯的，

假設你有 n 個版本 [1, 2, …, n]，你想找出導致之后所有版本出錯的第一個錯誤的版本，

你可以通過呼叫 isBadVersion(version) 介面來判斷版本號 version 是否在單元測驗中出錯，實作一個函式來查找第一個錯誤的版本，你應該盡量減少對呼叫 API 的次數，

示例:

給定 n = 5，并且 version = 4 是第一個錯誤的版本，

呼叫 isBadVersion(3) -> false
呼叫 isBadVersion(5) -> true
呼叫 isBadVersion(4) -> true

所以，4 是第一個錯誤的版本，

二、二分法解題

二分查找是一種基于比較目標值和陣列中間元素的教科書式演算法，

如果目標值等于中間元素，則找到目標值，
如果目標值較小，繼續在左側搜索，
如果目標值較大，則繼續在右側搜索，

時間復雜度：O(logN)，
空間復雜度：O(1)，

三、基礎模版II

確定初始的左右邊界:
- left: 0
- right: nums.length-1
- mid: (left + (right - left) >> 1)
查找條件需要訪問元素的直接右鄰居，
使用元素的右鄰居來確定是否滿足條件，并決定是向左還是向右，
保證查找空間在每一步中至少有 2 個元素，
需要進行后處理，當你剩下 1 個元素時，回圈 / 遞回結束，需要評估剩余元素是否符合條件，

四、題解

分析模版

我們的目標是：尋找出錯的版本
- 如果mid值出錯，證明出錯的版本 <= mid，那么右側就可以拋棄了
- 如果mid值沒出錯，證明出錯的版本 > mid，那么左側就可以拋棄了

看基礎模版II，版本判斷函式在幫助我們判斷mid值右側是否有錯誤的值，

Javasciprt 代碼

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let min = 0;
        let max = n;
        // 因為mid = mid = max是結束的源頭，所以不能相等
        while(min < max){
            let mid = min + ((max - min) >> 1);
            if(isBadVersion(mid)){
                // 出錯版本，可能是初始版本，所以保留
                max = mid;
            }else{
                min = mid + 1;
            }
        }
        return min;
    };
};

如果大家對 min < max 存在疑問，可以看下面的代碼

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let min = 0;
        let max = n;
        let ans;
        // 因為mid = mid = max是結束的源頭，所以不能相等
        while(min <= max){
            let mid = min + ((max - min) >> 1);
            if(isBadVersion(mid)){
                // 出錯版本，可能是初始版本，所以保存，同時跳過它
                ans = mid;
                max = mid - 1; // 注意這里
            }else{
                min = mid + 1;
            }
        }
        return ans;
    };
};