題目：

你是一個開發者，負責維護一個版本控制系統。每個版本的產品都是按順序發布的，例如 version 1, version 2, version 3, 等等。某個版本被標記為「壞版本」，所有之後的版本都被認為是壞的。

假設你有一個 API bool isBadVersion(version) 可用來檢查該版本是否是壞版本，要求你找出第一個壞版本。問題是要在 最小化 API 呼叫次數 的情況下解決。

範例：

假設有 5 個版本，且第 4 版是第一個壞版本。

n = 5, bad = 4
呼叫 isBadVersion(3) -> false
呼叫 isBadVersion(5) -> true
呼叫 isBadVersion(4) -> true
所以，4 是第一個壞版本。

解題思路

有軟體開發經驗的一定知道怎樣是最有效率的夾版本，就是不斷地二分法找下去，就是二元搜尋的應用之一，這題也是運用這個方法。

while (left < right) 直到 left 跟 right 相等才結束，

left = mid + 1; 表示 mid 已經是好版本，因此排除當前 mid 不再把 mid 納入搜尋範圍，

right = mid; 沒有 -1 是因為要把 mid 納入搜尋範圍，因為我們不知道它是不是第一個壞版本，也有可能是第 3 個壞版本等等，因此要把它留在搜尋範圍內，同時也讓 right 永遠指向壞版本，範圍最終縮小收斂到 right 指向第一個壞版本。

不使用 int mid = (left + right) / 2; 因為會有溢位問題，當 n 很大且第一個壞版本在很尾巴時，就會造成 left 跟 right 都很大，那麼加起來就會有加法溢位問題，所以改採用 left + (right - left) / 2;

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            //int mid = (left + right) / 2; // 有溢位問題
            int mid = left + (right - left) / 2; // 防止溢位
            if (isBadVersion(mid)) {
                right = mid; // 把 mid 納入範圍
            } else {
                left = mid + 1; // 不再把 mid 納入範圍
            }
        }
        return left;
    }
};

參考：
#278. First Bad Version