二分介绍
二分可以被分为两类
为什么要这样分?当我们有重复元素的时候,会出现边界问题,这样写可以有效避免。
二分步骤
右端点
左端点
代码
#include<iostream>
using namespace std;
const int N = 100010;
int arr[N];
int n,m,x;
//第一种情况 q[mid]=x的时候r也会左移,直到移到x的开始位置:分界点条件是a[mid]>=x
//第二种情况 q[mid]=x的时候l也会右移,直到移到x的结束位置:分界点条件是a[mid]<=x
//l=mid的时候mid=l+r+1>>1
//r=mid的时候mid=l+r>>1
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>arr[i];
while (m -- )
{
cin>>x;
int l=0,r=n-1;
while(l<r)
{
//先找左边的
int mid=l+r>>1;
if(arr[mid]>=x) r=mid;
else l=mid+1;
}
if(arr[l]!=x) puts("-1 -1");
else
{
cout<<l<<" ";
//再找右边的
int l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(arr[mid]<=x) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}