低 < high vs low<= high vs high - low > 二分查找中的 1

Question

我对二分搜索中循环的终止条件感到困惑。我还看到了一些使用

high - low > 1

的解决方案。我需要一些解释来了解何时使用

low < high

、

low <= high

和

high - low > 1

。

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 (r - l > 1) {
            long m = (l + r) / 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;
        }

        return (int)l;
    }
}

这是社论中的解决方案，我将 while 的条件更改为

l < r

，但这不起作用

Answer 1

终止条件是还有东西需要排序。 在上面这意味着 2 个元素。

r - l > 1

与

1 + l < r

相同，与

l < r

不同。