二元搜索和不变关系

Question

我正在阅读这篇文章，并试图弄清楚如何确定二进制搜索的不变关系。具体来说，在他给出的两个例子中，为什么这两个不变关系不同？有什么不同？

A [开始] <目标<A [结束]部分很明显，但是问题是在哪里放置=符号？

另一个问题是，我可以简单地将框架更改为：

int binarySearchFramework(int A[], int n, int target) {
    int start = start index of array - 1;
    int end = length of the A;
    while (end - start > 1) {
        int mid = (end - start) / 2 + start;
        if (A[mid] == target) return mid;
        if (A[mid] < target) {
            end = mid;
        } else {
            start = mid;
        }
    }      
   //not found
   ...
}  

这不如帖子中提供的那样好吗？

非常感谢！

Answer 1

您可以选择不变式。这是从实践中学到的技能。即使有经验，它通常也包含一些尝试和错误。选一个。看看情况如何。寻找机会选择另一种需要较少维护工作的机会。您选择的不变式可以对代码的复杂性和/或效率产生重大影响。

二元搜索中至少有四个合理的不变式选择：

a[lo] <  target <  a[hi]
a[lo] <= target <  a[hi]
a[lo] <  target <= a[hi]
a[lo] <= target <= a[hi]

您通常会看到最后一个，因为它最容易解释，并且不会涉及超出范围的数组索引的棘手初始化，而其他数组则是如此。

现在有是有原因的使用像不变 a[lo] < target <= a[hi]。如果您想始终找到目标的重复序列中的第一个，则该不变变量将执行O（log n）次。当时hi - lo == 1，hi指向目标的第一个匹配项。

int find(int target, int *a, int size) {
  // Establish invariant: a[lo] < target <= a[hi] || target does not exist
  // We assume a[-1] contains an element less than target. But since it is never
  // accessed, we don't need a real element there.
  int lo = -1, hi = size - 1;
  while (hi - lo > 1) {
    // mid == -1 is impossible because hi-lo >= 2 due to while condition
    int mid = lo + (hi - lo) / 2;  // or (hi + lo) / 2 on 32 bit machines
    if (a[mid] < target)
      lo = mid; // a[mid] < target, so this maintains invariant
    else
      hi = mid; // target <= a[mid], so this maintains invariant
  }
  // if hi - lo == 1, then hi must be first occurrence of target, if it exists.
  return hi > lo && a[hi] == target ? hi : NOT_FOUND;
}

注意，此代码未经测试，但应通过不变逻辑来工作。

带2的不变式<=只会找到目标的某个实例。您无法控制哪一个。

此不变量确实需要使用进行初始化lo = -1。这增加了证明要求。您必须显示mid永远不能设置为-1，这将导致超出范围的访问。幸运的是，这种证明并不难。

您引用的文章是糟糕的。它有几个错误和不一致之处。在其他地方查看示例。对Pearls编程是一个不错的选择。

您建议的更改是正确的，但可能会稍慢一些，因为它用一次迭代运行一次的测试代替了只能运行一次的测试。

Answer 2

你写了

A[start] < target < A[end] 部分很明显

但这显然是错误的，因为初始值应该是start = 0，end = N-1（而不是-1，N）。顺便说一句，对于链接中描述的情况（不同元素的数组），您不需要任何不变量。

这将毫无问题且易于理解。

int arr[] = {0,1,2,3,4,5,6,7};
int N = sizeof (arr) / sizeof (arr[0]);
int target = 4;

int l = 0, r = N-1;
while( l <= r ) {
    int mid = (l+r)>>1;
    if( arr[mid] == target )
        return mid;
    if( arr[mid] < target )
        l = mid + 1;
    else
        r = mid - 1;
}
return -1; // not found