用于查找元素第一次出现的二分搜索的不变量

Question

我在定义查找二分查找第一个元素的不变量时遇到问题。（我有一个排序数组 a，我想找到第一个等于某个数字 q 的元素，如果它不存在 return -1）

首先，我暂时设置了这个不变量。

我的不变量

"Always a[l]<= q and also a[r] > q" ==> "Always l <= ind and also > ind".

根据我的不变量，我写了这段代码：

int l=0,r=n;
while(l<r){
    int mid=(r+l)/2;
    if(a[mid]==q){
        r=mid+1;
    }
    else{
        if(a[mid]>q){
            r=mid;
        }else if(a[mid]<q) l=mid+1;
    }
}
return l;

但是有一个问题 if(a[mid]==q) 那么我必须选择一个 r 不违反我的不变量。

如果我选择mid-1我会违反它因为a[r]将<=q.

而且我必须遍历我的索引，直到找到 a[i]>q 的索引，然后将 r 设置为该索引。 (r=i)==>但是如果我这样做就不是 O(log n)

而且我已经看到一些实现 lower_bound 的代码 if(a[mid]==q) 将 r 设置为 mid 但我认为它们违反了它们的不变性但它们的代码是正确的并且return 正确值。

喜欢这个代码：

1- int l = 0;
2- int r = n; // Not n - 1
3- while (l < r) {
4-     int mid = (l + r) / 2;
5-     if (q <= a[mid]) {
6-         r = mid;
7-     } else {
8-         l = mid + 1;
9-     }
10- }
11- return l;

首先，不变量就像我的不变量（i 在 [l,r) 的范围内）但是在第 5 行考虑 if(q==a[mid]) 然后显然它违反了因为它（ [l,r] 因为 r 是相等的并且它可以是第一次出现）。

我说的对还是我没有正确理解不变量的概念？

Answer 1

假设我们有一个序列

..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                 ^ (*)

其中 <q (>q) 代表任何元素 < q (> q)。我们要找到点 (*)。

我们有两个指针，left < right。我们如何使用它们来区分那个点？答案很简单：left 应该指向最后一个 <q 元素，right 应该指向第一个 q 元素：

..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                 ^ right
             ^ left

不变量是：*left < q和*right >= q。

您建议的不变量 *left <= q 和 *right > q 对应于该序列中的最后一个元素：

..., <q, <q, <q, q, q, ..., q, q, >q, >q, >q, ...
                                  ^ right
                               ^ left

一些有用的参考资料：

第 4 栏：编写正确的程序 – J.Bentley。 编程珍珠。 Addison-Wesley，2^nd 版，1999 年。 Book website
J.Bentley。 编程明珠：编写正确的程序。 ACM 通讯 26, 1040 (1983)。 Full text
二进制搜索的不变量 – Dr.Dobb's Journal Part I, Part II, Part III, Part IV, Part V, Part VI, Part VII, Part VIII, Part IX, Part X

用于查找元素第一次出现的二分搜索的不变量

invariant of binary search for finding first occurrence of an element

c++

algorithm

binary-search

invariants