二分查找循环终止条件解析：三种判断条件的适用场景

三种终止条件的适用场景 #

• low <= high：标准闭区间查找，适合需要精确匹配目标值的场景（比如判断数组中是否存在某元素）。循环结束时low > high，说明整个区间已遍历完毕，无匹配项。
• low < high：多用于寻找边界值（第一个/最后一个满足条件的元素），循环结束时low == high，这个值就是目标边界。注意要根据指针移动逻辑调整mid的取整方式（向下/向上），避免死循环。
• high - low > 1：区间收缩到相邻元素时停止，属于边界查找的变种。循环结束后low和high相邻，需根据问题需求选择其中一个作为结果。这种方式不用纠结mid取整，不会死循环，适合寻找最大的满足条件的值（比如你的代码场景）。

你的代码为什么改条件后无法运行 #

原代码的逻辑是寻找最大的m，使得extra >= 0，原终止条件r - l >1会让最终l停在最后一个满足条件的值，r停在第一个不满足的值，直接返回l即可。

改成l < r的问题与修复 #

原逻辑中extra >=0时l=m，如果用l < r且mid=(l+r)/2（向下取整），当区间只剩两个元素时，mid等于l，此时若满足条件，l=m会导致区间不再收缩，触发死循环。

修复方式：把mid改成向上取整，同时调整右边界的移动逻辑：

class Solution {
    public static int maxValueArray(int n, int k, int[] arr) {
        long l = Arrays.stream(arr).min().getAsInt() - 1;
        long r = 1_000_000_001;

        while (l < r) {
            // 向上取整，避免区间长度为2时的死循环
            long m = l + (r - l + 1) / 2;

            long extra = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] > m)
                    extra += (arr[i] - m) / k;
                else
                    extra -= (m - arr[i]);
            }

            if (extra >= 0)
                l = m; // 满足条件，尝试更大的值
            else
                r = m - 1; // 不满足，缩小右边界
        }

        return (int)l;
    }
}

改成l <= r的问题与修复 #

这种闭区间查找需要主动记录满足条件的最大值，因为循环结束时l > high，原逻辑直接返回l或r会出错。

修复方式：新增变量记录符合条件的m，每次满足条件时更新记录，并尝试更大的值；不满足则缩小右边界：

class Solution {
    public static int maxValueArray(int n, int k, int[] arr) {
        long l = Arrays.stream(arr).min().getAsInt() - 1;
        long r = 1_000_000_001;
        long res = l; // 记录满足条件的最大值

        while (l <= r) {
            long m = l + (r - l) / 2;

            long extra = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] > m)
                    extra += (arr[i] - m) / k;
                else
                    extra -= (m - arr[i]);
            }

            if (extra >= 0) {
                res = m; // 更新满足条件的最大值
                l = m + 1; // 尝试更大的值
            } else {
                r = m - 1; // 缩小右边界
            }
        }

        return (int)res;
    }
}

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