一、模板示范
闫而总之,只要所要寻找的数组能够满足某一条件而被分成两边,就能进行二分,这边我们就拿有序数组的二分来做例子;
假设目前有这么一组数据:1 2 2 3 3 4 下标从0开始
假设此时的情景为,需要我们找到第一个>=3的数字,试想一下,如果能把整个区间分了两半,左边是<3的区间,右边是>=3的区间 如图:
那么右区间的第一个点,就是我们找到的符合>=3的第一个数字,将区间分为两半,是不是非常清晰!
我先给出代码实现(不要害怕 马上就能见证奇迹)
#include<iostream>
using namespace std;
int main()
{
int a[6]={1,2,2,3,3,4};
int l=-1,r=6;//定义两个指针
while(l+1!=r)
{
int mid=l+r>>1;//(相当于(l+r)/2)
if(a[mid]<3) l=mid;//或者if(a[mid]>=3) r=mid;
else r=mid; // else l=mid;
}
cout<<"第一个3所在的下标为 "<<r<<endl;
return 0;
}
返回的结果为:第一个3所在的下标为 3
最后二分的结果就是下面这个图,是我们想要的样子!
然后因为我们要找到的是第一个>=3的数字,所以就取 r 也就是>=3区间的第一个数字;
二、模板
对于一个有序数组,假设下标为0,1,2,3…,n-1;总共n个数字
那么模板为
int L=-1,R=n;
while(L+1!=R)
{
int mid=L+R>>1;
if(check()) L=mid;
else R=mid;
//最后根据你所分左右两边区间的结果
//选取L或者R作为结果
}
三、细节说明
为什么L的初始值为-1,R的初始值为N
首先,如果二分本来就没有结果
比如对于本文例题 1 2 2 3 3 4,,如果你要寻找第一个 >=5 的数,你会发现,整个过程都在执行L=mid,最后得到的结果中,R是等于下标6的,他明显这个时候是越界的,说明我们找不到要寻找的数字,而如果我们一开始将R赋值为n-1,也就是赋值为下标5的时候,他返回的R是5,是没有越界的,被我们当成了答案,但其实这时候我们的二分是没有答案的,就发生了错误;
其次,L最小值为-1,R最小值只能取到1,因为L+1!=R为循环结束条件,R最大值为N,同理则L的最大值为N-2,则(L+R)/2的取值范围是 [0,N)
mid的值始终位于0到N的左闭右开区间里面,不会发生越界的错误;
为什么循环结束的条件是while(L+1!=R)?
之前学过二分的小伙伴可能会发现,之前学的二分,他循环结束的条件是while(L<R)
而这边给出的循环条件是while(L+1!=R) 其实,就是当L和R相邻的时候,循环就结束,而原本的while(L<R)
是当两区间重合以后,循环才结束,所以之前我们需要判断对mid进行加一或者减一的操作,而且因为区间重合的问题,最后返回的L、R还要再进行判断,而这边的这个二分,因为区间反回的是不重合的两区间,只有L=mid和R=mid这两种情况,最后根据需要返回L或者R;
不会陷入死循环
对于比较奇葩的情况,比如数组大小为1或者2
比如int a[1],b[2];
由于我们是while(L+1!=R)结束循环,也就是当L和R相邻的时候结束条件
对于a[1],他的下标为0 此时L=-1,R=n也就是1
对于b[2],他的下标为0,1 此时L=-1,R=n也就是2
所以无论何种情况,初始的L+1始终小于R,历经循环后最终L和R相邻,不会出现一开始L就和R重合等情况导致出现while(L+1!=R)循环不能结束的情况文章来源:https://www.toymoban.com/news/detail-783670.html
最后
我们就能够通过二分得到不重合的两区间,而且只需要L=mid和R=mid,不需要考虑L=mid+1,R=mid-1的情况
且记得一开始对于一个下标为0,1,2…n-1的数组,指针L要赋值为-1,指针R要赋值为n,那么你就学会了
最后我给出y总基础算法中的二分例题
数的范围的这题的关于这个二分方法的代码实现文章来源地址https://www.toymoban.com/news/detail-783670.html
数的范围
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,q[N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
while(m--)
{
int k;scanf("%d",&k);
//寻找第一个等于K的坐标 我这边让二分的边界定为 左边为<5 右边>=5 则所求为r
int l=-1,r=n;
while(l+1!=r)//当l与r没有相接的时候,求边界
{
int mid=l+r>>1;
//下面找第一个>=5的坐标
if(q[mid]>=k) r=mid;
else l=mid;
}
//此时得到的r是第一个>=5的坐标
if(q[r]!=k) printf("-1 -1\n");
else{
printf("%d ",r);
//现在找最后一个<=5的数字 我这边让二分的左边为<=5 右边为>5 则所求为ll
int ll=-1,rr=n;
while(ll+1!=rr)
{
int mid=ll+rr>>1;
if(q[mid]<=k) ll=mid;
else rr=mid;
}
if(q[ll]!=k) printf("%d\n",r);
else printf("%d\n",ll);
}
}
}
四、
例题one数的范围
例题two数的三次方根
五、相关学习的视频链接-为啥二分查找容易出错
到了这里,关于不需要考虑mid+1、mid-1的二分查找模板,希望大家都能学会的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!