这篇文章解决若干问题:
如果递增序列A中的元素可能重复,那么如何对给定想查找的元素x:
- 求出序列中第一个大于等于x的元素的位置;
- 求出序列中第一个大于x的元素的位置;
- 求出序列中第一个满足某条件的位置;
- 求出序列中最后一个小于等于x的元素的位置;
- 求出序列中最后一个小于x的元素的位置。
第一个大于等于x和第一个大于x的元素的位置
举个栗子:对数组序列{1,3,3,3,6}(下标从0开始)来说,若查询3,则得到L=1、R=4。
如果查询8,则得到L=R=5。
如果序列中没有x,那么L和R也可以理解为假设序列中存在x,则x应当在的位置。
现在,来解决第一个小问吧。
如果已经对二分查找能单独根据脑子里的想的写出代码的时候,lower_bound和upper_bound也能写出来。下面给出代码,读者可以尝试画个数组后按代码中算法推导出来。
其中注意:
对于lower_bound
第一
循环条件为left<right
,而不是二分查找的left<=right
。在二手查找的问题中,需要元素不存在时返回-1,这样当left>right
时[left,right]
就不再是闭区间(失去比较的意义),因此可以作为元素不存在的判定规则。
但是如果想要返回第一个大于等于x的元素的位置,就需要判断元素x本身是否存在(就算不存在,返回的也是“若存在应该在的位置”),于是乎当left<right
时让循环一直执行即可。
第二
由于left==right
时while循环终止,因此最后的返回值既可以是left,也可以是right。
最后
二分的初始区间的原则是应当能覆盖到所有可能返回的结果。
二分下界0可以确定,但是上界是n还是n-1?考虑到想要查询元素x有可能比序列中所有元素都要大,此时应该返回n(若n在数列中存在则它应该在的位置)。因此上界为n。
二分的初始区间为[left,right]=[0,n]
。
代码如下:
//left=0 right=n(注意不是n-1)
int lower_bound(int A[],int left,int right,int x){ //对于元素x,就算不存在于A中,也可以返回所需要的值
int mid;
while(left<right){ //left==right意味着找到了唯一的位置
mid=(left+right)/2;
if(A[mid]>=x){
right=mid;
}
else{
left=mid+1;
}
}
return left; //返回查找的位置(当left==right时,循环停止,所以此时left=right)
}
int upper_bound(int A[],int left,int right,int x){
int mid;
while(left<right){
mid=(left+right)/2;
if(A[mid]>x){
right=mid;
}
else{
left=mid+1;
}
}
return left;//返回查找的位置(此时left>right,left即为第一个大于x的元素的位置)
}
第一个满足某条件 C 的位置
寻找有序序列中第一个满足某条件 C 的元素的位置
代码如下:
//二分区间为左闭右闭的[left, right],初值必须能覆盖解的所有可能取值
int solve(int left, int right)
{
int mid;
while(left < right)//对于[left,right],两者相同即找到唯一位置
{
mid = left + right / 2;
if (条件成立) //条件成立,第一个满足条件的元素的位置 <=mid
{
right = mid; //往左子区间[left, mid]找
}
else //条件不成立,第一个满足该条件的位置>mid
{
left = mid + 1; //往右子区间[mid+1, right]找
}
}
return left; //最后返回夹出来的位置
}
举个栗子:
想要求第一个满足大于等于10的元素,则可以这样写。
代码如下:
#include<stdio.h>
//二分区间为左闭右闭的[left, right],初值必须能覆盖解的所有可能取值
const int n = 10;
int solve(int A[], int left, int right)
{
int mid;
while(left < right)//对于[left,right],两者相同即找到唯一位置
{
mid = (left + right) / 2;
if (A[mid] >= 10) //条件成立,第一个满足条件的元素的位置 <=mid
{
right = mid; //往左子区间[left, mid]找
}
else //条件不成立,第一个满足该条件的位置>mid
{
left = mid + 1; //往右子区间[mid+1, right]找
}
}
return left; //最后返回夹出来的位置
}
int main(){
int a[n] = {2,5,8,11,13,14,18,20,22,25};
printf("%d\n",solve(a,0,n));
return 0;
}
如果寻找最后一个满足“条件C”的元素的位置,则可以先求第一个满足“条件!C”的元素的位置。(比如,最长回文子串就用到了这一点)
先挖个坑,以后回来补
模板拓展(区间左开右闭)
实际上这种左开右闭区间的写法与左闭右闭区间的写法是等价的。
在这种写法下,循环条件变成了left + 1 < right,并且当left+1==right退出循环,使得(left,right]是唯一位置。
由于从左闭变成了左开,因此left的初值要比解的最小值小1(例如对下标为0序列,left的初值为-1,而right的初值不变,还是n),同时,left=mid+1应该改成left=mid(这里想想为什么?挖坑,待解决),并且,返回的值应该是right,而不是left。//二分区间为左闭右闭的(left, right],初值必须能覆盖解的所有可能取值 int solve(int left, int right) { int mid; while(left + 1 < right) { mid = (left + right) / 2; if (条件成立) //条件成立,第一个满足条件的元素的位置 <=mid { right = mid; } else //条件不成立,第一个满足该条件的位置>mid { left = mid; } } return right; }
举个栗子:
同样求第一个大于等于10的元素。
代码如下:#include<stdio.h> //二分区间为左开右闭的(left, right],初值必须能覆盖解的所有可能取值 const int n = 10; int solve(int A[], int left, int right) { int mid; while(left + 1 < right)//对于[left+1,right],两者相同即找到唯一位置 { mid = (left + right) / 2; if (A[mid] >= 10) //条件成立,第一个满足条件的元素的位置 <=mid { right = mid; //往左子区间[left, mid]找 } else //条件不成立,第一个满足该条件的位置>mid { left = mid; //往右子区间[mid, right]找 } } return right; //最后返回夹出来的位置 } int main(){ int a[n] = {2,5,8,11,13,14,18,20,22,25}; printf("%d\n",solve(a,-1,n)); return 0; }
输出:3
值得注意的是,如果solve函数中返回的是left,则输出2。
最后一个小于等于x和最后一个小于x的元素的位置
既然我们现在已经能求出序列中第一个大于等于x的元素的位置和第一个大于x的元素的位置这种问题了。
那怎么求出最后一个小于等于x的位置和求出最后一个小于x的位置?
只要按照lower_bound和upper_bound的算法自己进行推算,就能出答案了,下面是博主自己根据上面推算的代码。如果有错误,请指正。
代码:
#include <iostream>
using namespace std;
int lower_bound(int A[], int left, int right, int x){
int mid;
while(left <= right){
mid = (left + right) / 2;
if(A[mid] <= x)
left = mid + 1;
else
right = mid -1;
}
return right;
}
int upper_bound(int A[], int left, int right, int x){
int mid;
while(left <= right){
mid = (left + right) / 2;
if(A[mid] < x)
left = mid + 1;
else
right = mid -1;
}
return right;
}
int main(){
int n, x;
cin>>n;
cin>>x;
int a[n];
for(int i = 0; i < n; i++)
{
cin>>a[i];
}
cout << lower_bound(a, 0, n-1, x) <<" "<< upper_bound(a, 0, n-1, x);
return 0;
}
这里提供另外一种参数仅供参考:
int lower_bound(int a[], int n, int x){
int left = 0 , right = n - 1, mid;
......
}
int upper_bound(int a[], int n, int x){
int left = 0 , right = n - 1, mid;
......
}
int main(){
......
cout << lower_bound(a, n, x) <<" "<< upper_bound(a, n, x);
......
}
参考
版权所有:可定博客 © WNAG.COM.CN
本文标题:《二分查找的延伸》
本文链接:https://wnag.com.cn/833.html
特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~
叨叨几句... NOTHING