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

invariant of binary search for finding first occurrence of an element

我在定义查找二分查找第一个元素的不变量时遇到问题。 (我有一个排序数组 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 是相等的并且它可以是第一次出现)。

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

假设我们有一个序列

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

一些有用的参考资料: