二分查找函数处理含负数测试用例时超时问题求助

你的二分查找函数超时的核心原因是中间索引计算的运算顺序错误，和数组中包含负数没有直接关系——只是这个测试用例刚好触发了死循环。

问题细节 #

你当前计算middleIndex的代码是：

let middleIndex = Math.floor(leftIdx + rightIdx / 2);

由于JavaScript中除法优先级高于加法，实际执行逻辑是leftIdx + (rightIdx / 2)，这完全偏离了二分查找需要的(leftIdx + rightIdx) / 2的中间值计算逻辑。

拿你给出的测试用例arr = [-1,0,3,5,9,12]、目标值9来举例：

1. 初始leftIdx=0，rightIdx=5，计算得middleIndex=0 + 5/2=2.5，取整后为2，对应值3。因为9>3，leftIdx被设为3。
2. 接下来leftIdx=3，rightIdx=5，计算得middleIndex=3 +5/2=5.5，取整后为5，对应值12。因为9<12，rightIdx被设为4。
3. 此时leftIdx=3，rightIdx=4，计算得middleIndex=3 +4/2=5，但rightIdx=4，arr[5]还是12。9<12，rightIdx再次被设为4。
4. 从此进入死循环：leftIdx=3、rightIdx=4的状态永远无法改变，也找不到目标值9，最终导致超时。

修正方案 #

把中间索引的计算改为先求和再除法，确保运算顺序正确：

function binarySearch(arr, val){
    let leftIdx = 0;
    let rightIdx = arr.length - 1
  
    while(leftIdx <= rightIdx){
        // 修正运算顺序，先求和再除以2
        let middleIndex = Math.floor((leftIdx + rightIdx) / 2);
        let middleVal = arr[middleIndex]
        
        if(val < middleVal){
            rightIdx = middleIndex - 1
        } else if(val > middleVal){
            leftIdx = middleIndex + 1
        } else {
            return middleIndex
        }
    }
    return -1
}

如果要避免极端情况下的数字精度问题（比如数组长度极大时），也可以用Math.floor(leftIdx + (rightIdx - leftIdx)/2)来计算中间索引，逻辑是等价的。

内容的提问来源于stack exchange，提问作者Sean Whitty