二分介绍
二分可以被分为两类
为什么要这样分?当我们有重复元素的时候,会出现边界问题,这样写可以有效避免。
二分步骤
右端点
左端点
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n,q,x;
int a[N];
int main()
{
cin>>n>>q;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
while(q--)
{
cin>>x;
int l=0,r=n-1;
//找左端点
while(l<r)
{
int mid=l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x) cout<<-1<<" ";
else cout<<l<<" ";
//找右端点
l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
if(a[l]!=x) cout<<-1<<endl;
else cout<<l<<endl;
}
return 0;
}