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.
假设从1-n有n个versions，从一个x以后，全是bad version，找到第一个bad version，要求尽量少调用bool isBadVersion(version) 这个函数。折半查找。一个 left初值是1，一个right初值是n，一个mid是（left+right）/2。判断mid是不是bad version。如果是，则目标在left - mid区间里。如果不是，目标在mid+1 - right区间里（因为mid不是bad version，责肯定不是第一个bad version，所以这里从 mid+1往后找）。还遇到一个，特别大的数，left + right 超过int 范围了，就把这几个数改成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;
}
};
