JavaScript用for循环实现二分查找测试用例失败，求问题原因

问题原因分析 #

你代码的核心问题是错误引入了无关的循环计数变量i，用i <= end作为循环终止条件：

• for循环中的i是从初始值0开始持续递增的，而end变量在二分查找过程中会随着查找范围缩小不断变小
• 当i递增到大于当前的end值时，循环会提前终止，此时还没完成全部查找逻辑，自然就找不到存在的元素
  比如你尝试查找测试用例1数组的第一个元素5时，当end被更新为0时，i已经递增到3，3 <= 0条件不成立，循环直接退出，不会执行最后一次判断逻辑，直接返回-1。你测试用例2能通过只是巧合，刚好在i超过end前就找到了目标值。

修复方案 #

直接删除计数变量i，将循环条件改为start <= end即可，二分查找不需要额外的计数变量，只需要判断左右边界是否交叉：

function binarySearch(arr, val){
    let start = 0
    let end = arr.length - 1
    let middle = Math.floor((start + end)/2)
    // 替换原来的for循环，用start <= end作为循环条件
    while(start <= end) {
        if(val === arr[middle]) { 
           return middle
        }
        if(val < arr[middle]){
            end = middle - 1
        } else {
           start = middle + 1
        }
        middle = Math.floor((start + end)/2)
    }
    return -1
}

如果一定要用for循环实现，可以写成：

function binarySearch(arr, val){
    let start = 0
    let end = arr.length - 1
    let middle
    for(; start <= end; middle = Math.floor((start + end)/2)){
        middle = Math.floor((start + end)/2)
        if(val === arr[middle]) { 
           return middle
        }
        if(val < arr[middle]){
            end = middle - 1
        } else {
           start = middle + 1
        }
    }
    return -1
}

内容的提问来源于stack exchange，提问作者Nishant Kumar