何时对循环不变使用低<高或低 + 1 <高

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 < highCCD_ 4。

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

有人能澄清为什么以及何时我们可能希望在while循环中使用low + 1 < high而不是low < high吗？

Answer 1

如果不变量是目标必须位于low <= i <= high中，则使用while (low < high)；如果不变量是目标必须位于low <= i < high中，则使用while (low + 1 < high)。[感谢David Eisenstat的确认。]