题目描述
给定一个按照升序排列的长度为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
整数二分步骤
先找左端点,q[mid]>=x;再找右端点,q[mid]<=x(或者l从左端点开始,q[mid]==x)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m;
int q[N];
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)scanf("%d",&q[i]);
for(int i=0;i<m;i++){
int x;
scanf("%d",&x);
//二分x的左端点
int l=0,r=n-1;//确定区间范围
while(l<r){//当区间中只剩下一个数,即l==r时while停止
int mid=r+l>>1;
if(q[mid]>=x)r=mid;//找到第一个大于等于x的值(while结束后再判断是否成立),若mid>=x则r大或者正好了,r=mid;
else l=mid+1;//反之,l小了且mid取不到,l=mid+1;
}
if(q[r]==x){
cout<<r<<" ";
//二分的右端点
r=n-1;//右端点一定在[左端点,n-1]之间
while(l<r){
int mid=r+l+1>>1;//由于l=mid,所以要补上+1
if(q[mid]<=x)l=mid;//同理(这里改为==也是可以的,因为l是从左端点开始的)
else r=mid-1;
}
cout<<l<<endl;
}
else cout<<-1<<" "<<-1<<endl;
}
return 0;
}