何时使用低<高或低+ 1<循环不变高 [英] When to use low < high or low + 1 < high for loop invariant

问题描述

我已经阅读了多篇文章，包括关于二进制搜索的乔恩·本特利(Jon Bentleys)一章.这是我对CORRECT二进制搜索逻辑的了解，并且可以在我做的简单测试中起作用:

I've read multiple articles including Jon Bentleys chapter on binary search. This is what I understand about CORRECT binary search logic and it works in the simple tests I did:

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行而不是返回

Now to find the 1st occurence with sorted duplicates, you'd chance line 3 if condition to continue instead of returning 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

Similarly to get highest index of repeated element, you'd do low = mid + 1 and continue if arr[mid]==k

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

This logic seems to be working but in multiple places I see the loop invariant as

while (low + 1 < high)

我很困惑，想了解您何时想使用 low + 1<高的 low<高.

I am confused and want to understand when you might want to use low + 1 < high instead of low < high.

在上述逻辑中， low + 1<如果您举一个简单的例子进行测试，那么高条件会导致错误.

In the logic I described above low + 1 < high condition leads to errors if you test with simple example.

有人可以说明为什么和何时我们想使用 low + 1<高，而不是 low<高?

Can someone clarify why and when we might want to use low + 1 < high in the while loop instead of low < high?

推荐答案

如果不变的是目标必须位于 low< = i< = high 中，则可以使用而(低<高);如果您的不变项是目标必须位于 low< = i<高，然后使用 while(低+ 1 <高).[感谢David Eisenstat确认这一点.]

If your invariant is that the target must lie in low <= i <= high, then you use while (low < high); if your invariant is that the target must lie in low <= i < high then you use while (low + 1 < high). [Thanks to David Eisenstat for confirming this.]

这篇关于何时使用低<高或低+ 1<循环不变高的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！