You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

假設(shè)從1-n有n個(gè)versions，從一個(gè)x以后，全是bad version，找到第一個(gè)bad version，要求盡量少調(diào)用bool isBadVersion(version) 這個(gè)函數(shù)。折半查找。一個(gè) left初值是1，一個(gè)right初值是n，一個(gè)mid是（left+right）/2。判斷mid是不是bad version。如果是，則目標(biāo)在left - mid區(qū)間里。如果不是，目標(biāo)在mid+1 - right區(qū)間里（因?yàn)閙id不是bad version，責(zé)肯定不是第一個(gè)bad version，所以這里從 mid+1往后找）。還遇到一個(gè)，特別大的數(shù)，left + right 超過int 范圍了，就把這幾個(gè)數(shù)改成long就過去了。
代碼如下：

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

class Solution {
public:
    int firstBadVersion(int n) {
        long left = 1;
        long right = n;
        long mid = (left+right)>>1;
        while(right!=left)
        {
            if(isBadVersion(mid))//是 前 //不是 后
            {
                right = mid;
                
            }
            else left = mid+1;
            mid = (left + right)>>1;
        }
        return mid;
    }
};