讨论/《初级算法》 - 第一个错误的版本/
《初级算法》 - 第一个错误的版本
这版本在每次API call时会根据目前是否好坏版本 加多了前或后的版本的检查,
average case 会有所提升

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 0, end = n, mid = 0;

        //一直找到最后一个
        while(start != end){
            mid = start+(end-start)/2;
            if (isBadVersion(mid)) {
                if(!isBadVersion(mid-1)) return mid;
                end = mid;
            }  else {
                if(isBadVersion(mid+1)) return mid+1;
                start = mid+1;
            }
        }

        return end; 
    }       
}
展开全部 30 讨论