第一個錯誤的版本

你是產品經理，目前正在領導一個團隊開發一個新產品。不幸的是，您的產品的最新版本沒有通過質量檢查。由於每個版本都是基於之前的版本開發的，所以錯誤版本之後的所有版本都是不好的。

假設你有 n 個版本 [1, 2, ..., n]，你想找出第一個錯誤的版本，導致下麵所有的錯誤。

你可以通過 bool isBadVersion(version) 的介面來判斷版本號 version 是否在單元測試中出錯。實現一個函數來查找第一個錯誤的版本。您應該儘量減少對 API 的調用次數。

很容易想到二分法，時間複雜度為log(N),然後寫瞭如下代碼

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
　　int l=0;
　　int r=n;
　　int mid=0;
　　while(l<r)
　　{
　　　　mid=(l+r)/2;
　　　　if(!isBadVersion(mid))
　　　　　　l=mid+1;
　　　　else
　　　　　　r=mid;
　　}
　　return l;
　}
};

然後自信滿滿提交，發現在過接近int範圍的大數時出錯了，百度下看了別人的代碼才發現，

(l+r)/2在處理大數時會超出int範圍，

從而修改代碼

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
int firstBadVersion(int n) {
　　int l=0;
　　int r=n;
　　int mid=0;
　　while(l<r)
　　{
　　mid=l+(r-l)/2;
　　if(!isBadVersion(mid))
　　　　l=mid+1;
　　else
　　r=mid;
　　}
　　return l;
　　}
};

成功過。