5

我已经阅读了多篇文章，包括 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

现在要找到第一次出现的排序重复项，如果条件继续而不是返回 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？

4

1 回答 1

3

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

于 2013-08-12T22:46:40.690 回答