我的算法：
public class Solution extends VersionControl { private static final int ALL_NOTBAD = 1; private static final int ALL_BAD = 2; private static final int FIRST_BAD = 3; public int firstBadVersion(int n) { // 检索最快的永远是二分查找 int low=1; int high=n; int middle=n; while(low<high){ if(isfirst(middle) == FIRST_BAD) { // 如果是判断是第一bad的话 break; } else if(isfirst(middle)== ALL_BAD){ // 如果两个都是bad high = middle; } else { low = middle; } middle = low + (high-low)/2; } return middle; } private int isfirst(int n){ // 判断是否是first，需要考虑2种情况：1 当前是bad，但是前一个版本不是bad。2当前是bad，且当前为1 if((!isBadVersion(n-1) && isBadVersion(n))||(n == 1 && isBadVersion(n))){ // 当前版本不是badversion，且下一个版本是badversion return FIRST_BAD; } else if(isBadVersion(n) && isBadVersion(n-1)) { return ALL_BAD; } else { return ALL_NOTBAD; } } }大神的简洁算法：
public class Solution extends VersionControl { public int firstBadVersion(int n) { int low=1, high=n; while(low<high) { int mid=low + (high-low)/2; if(isBadVersion(mid)) { high = mid; } else { low = mid + 1; } } return low; } }这道题中又出现了二分查找的两个常见问题：
一定要对大数敏感，这个问题之前也遇到过，就是为什么 middle = low +（high-low）/2 这种写法相邻迷失问题，就是当 low 和 high是两个相邻的数，并且 high 为所求的时候，因为 middle 实际每次求都是 （low+high）/2 ，得出的依然是 low。所以永远解不出来> 解决方法： 可以按照我上面写的那样判断是否low，high相邻，更好的解决方法是 大神算法中的 low = middle+1