二分算法边界问题的讨论
为什么在l=mid的模板中,算中位数要额外+1?
cpp中,整数除法为向下取整
考虑只有两个数的情况[0,1](这里数组的数等于其下标方便比较)。mid=(0+1)/2=0而不是等于1,此时的l已经为0了,设判别函数满足要求需要进行迭代,而经过这次mid迭代后,mid仍然为0,所以就造成了死循环。
关于此题的一些要点
判断数字相等的左边界时保证右边的数都大于等于n,所以用r=mid的模板
右边界同理可得用l=mid的模板
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,q;
int a[N];
int fr(int num)
{
int l=0;
int r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(a[mid]>=num) r=mid;
else l=mid+1;
}
return l;
}
int fl(int num)
{
int l=0;
int r=n-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(a[mid]<=num) l=mid;
else r=mid-1;
}
return l;
}
int main()
{
cin>>n>>q;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
}
while (q -- )
{
int num;
cin>>num;
int ll=fr(num);
if(a[ll]!=num)
{
cout<<"-1 -1"<<endl;
continue;
}
int rr=fl(num);
cout<<ll<<" "<<rr<<endl;
}
return 0;
}