题目描述
给定一个按照升序排列的长度为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
算法1
C++ 代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int t;
int x;
void down(int x){
int l=1;
int r=n;
int f=-1;
while(l<r){
int mid=(l+r)/2;
if(x>a[mid]){
l=mid+1;
}
else{
r=mid;
}
}
if(a[l]!=x){
cout << "-1" ;
}
else{
cout << l-1 ;
}
}
void up(int x){
int l=1;
int r=n;
while(l<r){
int mid=(l+r+1)/2;
if(x>=a[mid]){
l=mid;
}
else{
r=mid-1;
}
}
if(a[l]!=x){
cout << "-1" ;
}
else{
cout << l-1 ;
}
}
int main()
{
cin >> n >> t;
for(int i=1;i<=n;i++){
cin >> a[i];
}
while(t--){
cin >> x;
down(x);
cout << " ";
up(x);
cout << endl;
}
return 0;
}