LeetCode/solutions/278. First Bad Version.md

# [278. First Bad Version](https://leetcode.com/problems/first-bad-version/description/)
# 思路
思路很简单，就是二分法。    
但是这题会超时，其实问题不是时间复杂度高(二分法的时间复杂度已经是理论最低了)，而是因为在计算`mid = (low + high) / 2`时low + high会溢出而产生不可预料的值。   
所以，我们不应该用`mid = (high + low) / 2`来更新mid而应该`mid = low + (high - low) / 2`。   
> **以后的二分法都应该这样更新mid以防溢出！！！**
# C++
```C++
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int low = 1, high = n, mid;
        while(low <= high){
            mid = low + (high - low) / 2; // mid = (high + low) / 2 会溢出！！！
            if(isBadVersion(mid)) high = mid - 1;
            else low = mid + 1;
        }
        return low;
    }
};
```