278. First Bad Version

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

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left+1<right){
            int mid =left + ( right - left ) / 2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid;
                /*why we cannot use mid＋1？
                since when n is 2147483647 
                if left = mid + 1
                when mid = 2147483646, right = 2147483647          
                left can be 2147483647, then when we go to 
                the while(left+1<right> again, 
                left+1 will cause overflow                
                */

            }
        }
        if(isBadVersion(left)){
            return left;
        }else{
            return right;
        }
    }
};