这道题我一开始觉得找到了起始位置再找到结束位置就可以了,所以我用了二分找边界的方法。
但是我运行之后发现不对,后来发现我把q当成target了。
#include<iostream>
using namespace std;
const int N=1e5;
int a[N];
//性质:<=target
//满足性质的可行区间:左段
int bsearch_2(int l,int r,int target)
{
while(l<r)
{
int mid=(l+r+1)>>1;
if(a[mid]<=target)
l=mid;
else
r=mid-1;
}
return l;
}
//性质:>=target
//满足性质的可行区间:右段
int bsearch_1(int l,int r,int target)
{
while(l<r)
{
int mid=(l+r)>>1;
if(a[mid]>=target)
r=mid;
else
l=mid+1;
}
return l;
}
int main()
{
//freopen("xxx.in","r",stdin);
//freopen("yyy.out","w",stdout);
int n,q,target,b1,b2;
cin >> n >> q;
for(int i=0;i<n;i++)
cin >> a[i];
while(q--)
{
cin >> target;
b2=bsearch_2(0,n-1,target);
b1=bsearch_1(0,n-1,target);
if(a[b2]==target && a[b1]==target)
cout << b1 << " " << b2 << '\n';
else
cout << "-1 -1" << '\n';
}
//fclose(stdin);
//fclose(stdout);
return 0;
}