二分查找和不变关系

我正在读这个post并试图弄清楚我们如何确定二分搜索的不变关系。具体来说，在他举的两个例子中，为什么这两个不变关系不同呢？是什么造成了不同？

A[start]

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

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
   ...
}  

这个是不是没有帖子里提供的那么好？

多谢！

你可以选择不变量。这是从实践中学到的技能。即使有经验，通常也会涉及一些尝试和错误。选一个。看看进展如何。寻找机会选择另一种需要较少维护工作的产品。您选择的不变量可以对代码的复杂性和/或效率产生显着的影响。

二分查找中的不变量至少有四种合理的选择：

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

您通常会看到最后一个，因为它最容易解释，并且不涉及使用超出范围的数组索引进行棘手的初始化，而其他方法则这样做。

现在那里is使用类似不变式的原因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;
}

注意此代码未经测试，但应该按不变逻辑工作。

两个不变量<=只会发现some目标的实例。你无法控制哪一个。

这个不变量does需要初始化lo = -1。这增加了证明要求。你必须证明这一点mid永远不能设置为-1，这会导致超出范围的访问。幸运的是这个证明并不难。

你引用的那篇文章很糟糕。它有几个错误和不一致之处。在其他地方寻找示例。编程珍珠是一个不错的选择。

您建议的更改是正确的，但可能会慢一些，因为它将仅运行一次的测试替换为每次迭代运行一次的测试。