LeetCode First Bad Version：二分查找首個壞版本防溢出

題目回顧

版本 1...n，某版本引入 Bug 後所有後續版本均壞。調用 API isBadVersion(version) 判斷。找首個壞版本，最小化 API 調用次數。

二分查找關鍵：防止中點計算溢出

mid = (low + high) / 2 在 low+high > INT_MAX 時溢出。
正確寫法：mid = low + (high - low) / 2

C++ 代碼

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

class Solution {
public:
    int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2; // 防溢出
            if (isBadVersion(mid)) high = mid - 1;
            else low = mid + 1;
        }
        return low; // low 停在第一個壞版本
    }
};

邏輯驗證

• 循環不變量：[1, low-1] 全好，[high+1, n] 全壞
• 退出時 low = high + 1，low 即第一個壞版本

總結

看似簡單的二分，中點計算溢出是經典陷阱。面試必須寫 low + (high-low)/2 或 (low+high)>>>1（無符號右移）。