[leetcode]First Bad Version

This problem is a variation of binary search, but be very careful about integer overflow when summing large numbers. The correct way to compute the midpoint is left + (right - left) / 2. I used long long instead.

 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);
    }
};