二分端点问题,这题总结了二分的两种情况,重点理解二分原理过程,便于自己修改和灵活运用
类似题目:
AcWing 680. 剪绳子(浮点二分)
AcWing 1227. 分巧克力
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
int a[100010];
int main()
{
int n,k,q;
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=0;i<n;i++) cin>>a[i];
while(q--)
{
cin>>k;
int r=n-1,l=0;
while(r>l)
{
int mid=r+l>>1;
if(a[mid]>=k) r=mid;//找最左边界
else l=mid+1;
}
int left=l;
l=0,r=n-1;
while(r>l)
{
int mid=r+l+1>>1;
if(a[mid]>k) r=mid-1;//会找右边界
else l=mid;
}
int right=l;
if(a[left]==k&&a[right]==k)
printf("%d %d\n",left,right);
else printf("-1 -1\n");
}
return 0;
}