我在定义查找二分查找第一个元素的不变量时遇到了问题。 (我有一个排序数组 a，我想找到第一个等于某个数字 q 的元素，如果它不存在，则返回 -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 的索引 I，然后将 r 设置为该索引。 (r=i)==>但是如果我这样做就不是O(log n)
而且我已经看到一些实现 lower_bound 的代码，if(a[mid]==q) 将 r 设置为 mid 但我认为它们违反了不变性，但它们的代码是正确的并返回正确的值。
像这样的代码:
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
一些有用的引用:
关于c++ - 用于查找元素第一次出现的二分搜索的不变量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56288667/