AcWing 789. 数的范围
原题链接
简单
作者:
Lyle2021
,
2021-01-17 16:49:54
,
所有人可见
,
阅读 277
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N];
int findst(int x){
int l=0,r=n-1;
while(r>l){
int mid=r+l>>1;//这里没加1的话
if(a[mid]>=x){
r=mid;
}else l=mid+1;//这里要加1
}
return l;
}
int finded(int x){
int l=0,r=n-1;
while(r>l){
int mid = r+l+1>>1;//这里加1的话
if(a[mid]<=x){
l=mid;//这里不用加1
}else r=mid-1;
}
return l;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
int x;
while(m--){
cin>>x;
int st,ed;
st=findst(x);
if(a[st]!=x){
cout<<-1<<' '<<-1<<endl;
}
else{
ed=finded(x);
cout<<st<<' '<<ed<<endl;
}
}
return 0;
}