何时使用 low < high 或 low + 1 < high for 循环不变式

我读过多篇文章，包括 Jon Bentley 的二分搜索章节。这就是我对正确的二分搜索逻辑的理解，它在我所做的简单测试中有效：

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 行 if 条件继续 而不是返回 mid as

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?

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