public int firstBadVersion(int n) { int low =1; int high = n; //[1,n]闭区间 while (low<=high){ //不会溢出 int mid = low + (high-low)/2; if(isBadVersion(mid)){ break; }else { low = mid+1; } } int result = low; //首次出错的地方，肯定是上一次[low,mid)之间 while(isBadVersion(result)){ result++; } return result; }
一开始觉得，有序，查找，那肯定是二分查找了。
只要找到出现的false，那么第一次出现的false，肯定是上一次的low和这一次的mid之间，那么只要从low开始循环就好。
但是会超时。
那就想一想，有什么办法能够找到第一次出现的元素呢？
找到false的时候不返回，而是向前缩小范围，因为每次找到同样的，都是向前缩小范围的，所以最后找到的，一定是第一个。
public int firstBadVersion(int n) { int low =1; int high = n; //[1,n]闭区间 //当low=high的时候就是结果 while (low<=high){ //不会溢出 int mid = low + (high-low)/2; if(isBadVersion(mid)){ //这个mid不能去掉，因为有可能这个就是第一个错误的地方 high = mid; }else { low = mid+1; } } return low; }
所以这种类型的二分查找，方法就是找到了就往前，没找到就往后，相等就是结果
排第一的答案，投机取巧
