[leetcode]First Bad Version

此题就是二分的变种，但是千万要注意大整数求和越界，正确的计算方式应该是 left + (right - left) / 2; 我使用的是 long long.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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

class Solution {
public:
    int bSearch(long long left, long long right) {
        if (left >= right) {
            return right;
        }
        long long middle = (left + right) / 2;
        if (!isBadVersion(middle)) {
            if (middle + 1 > right) return middle;
            if (isBadVersion(middle + 1)) return middle + 1;
            else return bSearch(middle, right);
        }
        else {
            return bSearch(left, middle);
        }
    }

    int firstBadVersion(int n) {        
        return bSearch(1, n);
    }
};