c语言实现lower_bound和upper_bound

时间:2022-03-03 06:59:58
lower_bound(int A*,int l,int r,int val);
对于有序数组求职为val的元素插入位置,第一个出现该元素的位置.
分析:
等待插入的元素是val,有序数列是A[](此处按照升序排列),寻找的范围是[l,r];
如果查找区间只存在一个元素 l==r;时.
只需要判断val>A[l]时返回插入下标是l+1:
否则val<=A[l]返回的下表是l(因为要找的插入位置,小于或者相等都会插入到查找位置)
否则如果存在l<r;(l>r为不合法的情况,或者如果l>r时交换l和r)
可以取中点m=(l+r)/2;
比较A[m],与val的值的大小.
如果:
1.val>A[m];则如果A[]中存在val,那么一定是在右边,因此令l=m+1;
2.val<A[m];则如果A[]中存在val, 那么一定是在左边,因此令r=m-1;
3.val=A[m];则如果A[]在m之前存在val,那么一定是在左边此时边界保留,或者不保留,令r=m;或者r=m-1(选择较好的m-1)
可以将二三合并为普遍情况r=m; (如果r=m-1没查到结果会出现到m处查到的情况,因此可以做这样的归并)
如果l<r 任意的m=(l+r)/2   <  (r+r)/2即为r,任意计算出的r'<r;
如果l<r 任意的m=(l+r)/2 + 1  > (l+l)/2 + 1 (即为l+1) l'>l;

对于任意区间范围内l<r;是区间都在缩小,不会出现死循环直到l==r;(此时问题可解) ;

一次算法描述可以是

int lower_bound(int *A,int L,int R,int val){
int l=L,r=R;
while(l<r){
int m=(l+r)/2;
if(val<=A[m]){
r=m-1;
}else{
l=m+1;
}
}
return val<=A[l]?l:l+1;
}
以一个例子说明
A[1]={1};
此时有l==r;
查找大值2;
由于2>A[(0+1)/2];
因此插入位置l+1,即为1;
查找相同值1;
插入位置是l,即为0.
查找小值0:
插入位置是0,即为0.


如果l<r
A[5]={1,2,2,2,2};
此时查找2 (r=m)
第i次查找
i= 1  2  3  4  
l= 0  0  0  1
r= 4  2  1  1
m= 2  1  0  退出循环返回l,即为1.
如果零r=m-1;
l= 0  0  1
r= 4  1  1
m= 2  0  退出循环返回1
因此可以看出将情况A[m]=val,将r=m-1,效率更高O(log2n);

upper_bound思想同理

描述可以是

int upper_bound(int *A,int L,int R,int val){
int l=L,r=R;
while(l<r){
int m=(l+r)/2;
if(val>=A[m]){
l=m+1;
}else
r=m-1;
}
return val>=A[r]?r+1:r;
}

int main(){
int a[10]={1,2,2,2,2,2,2,4,5,6};
printf("%d\n",lower_bound(a,0,9,2));
printf("%d\n",upper_bound(a,0,9,2));
return 0;
}
执行结果

c语言实现lower_bound和upper_bound