二分查找-2

本题来自力扣


题目说当一个版本错误后，后面的版本都出错，并且要尽可能的减少验证请求的发送，这就明显是一个考验二分法的题目。跟1~100猜一个数类似。

思路：
首先设置起始值和终止值0和n。我想到优先将收尾排除，因为如果是收尾为错误源的话，循环的次数是最多的，会遍历至最里面一层，进行whlie循环，求中间值，判断中间值是否是错误的，如果是错误的，（再进行判断前一个是否是错误，如果不是，则为错误源，如果是，则将起始值设置为中间值），如果中间值是正确的，就调整终止值为中间值 + 1。

var solution = function(isBadVersion) {
    
    return function(n) {
    
        let start = 0
        let end = n
        if(isBadVersion(start)) return start 
        if(isBadVersion(end) && !isBadVersion(end - 1)) return end 
        while(start <= end) {
    
            let min = Math.floor((end - start) / 2) + start
            if(isBadVersion(min)) {
    
                if(!isBadVersion(min - 1)) {
    
                    return min
                }
                end = min
            }else {
    
                start = min + 1
            }
        }
    };
};

官方答案的代码似乎更为简洁

var solution = function(isBadVersion) {
    
    return function(n) {
    
        let start = 0
        let end = n
        while(start < end) {
    
            let min = Math.floor((end - start) / 2) + start
            if(isBadVersion(min)) {
    
                end = min
            }else {
    
                start = min + 1
            }
        }
        return start
    };
};

首先还是设置起始值和终点值，开始进行遍历循环，求出中间值，根据中间值的结果去缩小起始和终止值得范围。直到缩小至起始终止相等，这个值就是错误源。值得注意的是在遍历是的判断不能是<=，如果起始值和终止值相等还进入循环，会陷入死循环。