algorithm - 何时使用 low < high 或 low + 1 < high for loop invariant

Question

我读过多篇文章，包括 Jon Bentley 的二分查找章节。这是我对 CORRECT 二进制搜索逻辑的理解，它在我所做的简单测试中有效:

binarysearch (arr, low, high, k)
    1. while (low < high)
        2. mid  = low + (high - low)/2
        3. if (arr[mid] == k)
               return mid
        4. if (arr[mid] < k )
               high = mid -1
        5. else 
               low = mid + 1

现在要查找第一次出现的已排序重复项，如果条件继续，您可能会遇到第 3 行而不是返回 mid 作为

binarysearch_get_first_occur_with_duplicates (arr, low, high, k)
    1. while (low < high)
        2. mid  = low + (high - low)/2
        3. if (arr[mid] == k)
               high = mid - 1
               low_so_far = arr[mid]
        4. if (arr[mid] < k )
               high = mid -1
        5. else 
               low = mid + 1
        return low_so_far

类似地，为了获得重复元素的最高索引，你会做 low = mid + 1如果 arr[mid]==k 则继续

这个逻辑似乎有效，但在多个地方我看到循环不变量为

while (low + 1 < high)

我很困惑，想了解您何时可能需要使用 low + 1 < high反而的 low < high .

在我上面描述的逻辑中low + 1 < high如果您使用简单示例进行测试，条件会导致错误。

有人可以阐明为什么以及何时我们可能想要使用 low + 1 < high在 while 循环中而不是 low < high ？

Answer 1

如果你的不变量是目标必须位于low <= i <= high , 然后你使用 while (low < high) ;如果你的不变量是目标必须位于 low <= i < high然后你使用 while (low + 1 < high) . [感谢 David Eisenstat 确认这一点。]