1 題目

??第一個壞版本（First Bad Version）

lintcode：題號——74，難度——medium

2 描述

??代碼庫的版本號是從 1 到 n 的整數。某一天，有人提交了錯誤版本的代碼，因此造成自身及之后版本的代碼在單元測試中均出錯。請找出第一個錯誤的版本號。
你可以通過 isBadVersion 的接口來判斷版本號 version 是否在單元測試中出錯。（調用 isBadVersion 的次數越少越好）

/**
* class SVNRepo {
*     public:
*     static bool isBadVersion(int k);
* }
* you can use SVNRepo::isBadVersion(k) to judge whether 
* the kth code version is bad or not.
*/

??樣例：

輸入：n = 5，first bad version is 4
輸出：4
解釋：

isBadVersion(3) -> false
isBadVersion(5) -> true
isBadVersion(4) -> true
因此可以確定第四個版本是第一個錯誤版本。

3 思路

??問題可以轉化為在類似“OOOOXXXX”的序列中尋找分割點的問題，如果不考慮時間復雜度的話，可以從頭遍歷，耗時O(n)，但是要求調用isBadVersion()接口的次數越少越好，在有序序列中的查找，考慮使用二分法將耗時降為O(log n)。

1. 找到中間位置的元素；
2. 與目標元素比較，確定目標元素所在的區間，縮小目標區間；
3. 重復以上操作，直到找到或者結束。

??套用之前的經典二分搜索^[1]的模版，注意事項如下：

1. 循環中與目標元素的比較變成了對isBadVersion()接口的調用；
2. 跳出循環之后，對剩下的兩個元素先檢查頭，再檢查尾。

3.2 圖解

3.2 時間復雜度

??算法的時間復雜度為O(log n)

3.3 空間復雜度

??算法的空間復雜度為O(1)

4 源碼

??注意事項：

1. C++調用靜態方法使用“類名::函數名”的方式;
2. 注意接口isBadVersion()的返回值，false表示好版本，true表示壞版本，不要搞反了。

??C++版本：

/**
* @param n: 版本號數
* @return: 第一個壞的版本號（序號從1開始）
*/
int findFirstBadVersion(int n) {
    // write your code here
    int start = 1;
    int end = n;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (SVNRepo::isBadVersion(mid) == true)
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }

    if (SVNRepo::isBadVersion(start) == true)
    {
        return start;
    }

    return end;
}