// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
//序列可看成（0,0,0,0,1,1,1,1,1,1,1,1,1,1）找第一个为1的数（可用lower_bound函数）
class Solution
{
public:
int firstBadVersion(int n) //版本序列为有序序列，可用二分查找
{
int left = 1,mid,right=n;
while(left<=right) //这里也可以写成<
{
mid = left + (right - left)/2; //防止（left+right）/2造成溢出风险
if(!isBadVersion(mid))
{
left = mid + 1; //为0时往右边找，left会移动到第一个为1的数的位置
}
else
{
right = mid - 1;//为1时往左边找，也可以写成right=mid
}
}
if(isBadVersion(left)) return left;
else return -1; //如果找不到就返回-1
}
};
/*
//一般的二分查找
while(left <= right) //注意这里为<=，因为要计算一次mid再返回
{
mid = left + (right - left)/2; //防止（left+right）/2造成溢出风险
if(a[mid]<key)
{
left = mid + 1;
}
else if(a[mid]>key)
{
right = mid -1;
}
else
{
return mid;
}
}
*/
