给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素,则返回“-1 -1”。
输入格式
第一行包含整数n和q,表示数组长度和询问个数。
第二行包含n个整数(均在1~10000范围内),表示完整数组。
接下来q行,每行包含一个整数k,表示一个询问元素。
输出格式
共q行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回“-1 -1”。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
#include<iostream>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll A[N];
int main()
{
ll n,k;
cin>>n>>k;
for(ll i=0;i<n;i++)cin>>A[i];
while(k--)
{
ll x;
cin>>x;
ll l=0,r=n-1;
while(l<r)
{
ll mid=l+r>>1; //更新为r时mid不用加 1;
if(A[mid]>=x)r=mid; //每次判断A[mid]是否大于等于x
//l 和r 每次向最左边的 x逼近;
// 如A[5]={5,5,5,5,5,5,5}; x=5;
// l=0,r=7,mid=3 A[mid]=5==5
// l=0,r=3,mid=1 A[mid]=5==5
// l=0,r=1,mid=0 A[mid]=5==5
// l==r==0 跳出循环;找到最左边的 x;
else l=mid+1;
}
//可能找不到;
if(A[l]!=x)cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
l=0,r=n-1;
while(l<r)
{
ll mid=l+r+1>>1; //当更新的是l时mid要加 1
//为了避免出现死循环;,
//例如当 l = 1,r =2 时,mid为1,
//如A[mid]<=x 成立,l仍热被更新为 1,进入
//死循环;
if(A[mid]<=x)l=mid; //找到最右边的x;
else r=mid-1;
}
cout<<l<<endl;
}
}
}