为什么我用while循环编写的binary search无法适配所有输入场景？

存在的逻辑疏漏 #

你的代码核心问题是mid计算规则和左边界更新逻辑冲突，会触发死循环：

• 当搜索区间仅剩两个元素（即l = r - 1）时，Math.floor((l + r)/2)的计算结果等于l，如果此时满足A[m] <= X，代码会执行l = m，l的值不会发生变化，循环条件l < r永远成立，程序陷入死循环。
  比如测试用例A = [1,3], X = 3就会触发该问题，原代码无法正常返回结果。

修复方案 #

根据你需要的查找目标（找第一个匹配项/最后一个匹配项），有两种常用修复方式：

方案1：适配原代码逻辑（查找最后一个等于X的下标） #

仅需将mid计算改为向上取整即可解决死循环问题，修复后代码如下：

function solution(A, X) {
    var N = A.length;
    if (N === 0) {
        return -1;
    }
    var l = 0;
    var r = N-1;
    while (l < r) {
        // 改为向上取整，避免两元素区间下mid等于l导致死循环
        var m = Math.floor((l + r + 1) / 2);
        if (A[m] > X) {
            r = m - 1;
        } else {
            l = m;
        }
    }
    return A[l] === X ? l : -1;
}

方案2：调整逻辑实现查找第一个等于X的下标 #

如果你需要查找第一个匹配X的位置，调整边界更新规则即可：

function solution(A, X) {
    var N = A.length;
    if (N === 0) {
        return -1;
    }
    var l = 0;
    var r = N-1;
    while (l < r) {
        var m = Math.floor((l + r) / 2);
        if (A[m] < X) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    return A[l] === X ? l : -1;
}

内容的提问来源于stack exchange，提问作者John Doe