给定一个按照升序排列的长度为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 5 -1 -1
#include<cstdio> #include<cstring> #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); //二分 的左端点 int l = 0, r = n - 1;//确定区间范围 while (l < r) { int mid = (l + r) / 2; if (q[mid] >= x) r = mid; else l = mid + 1; } if (q[r] == x) { cout << r << " "; //二分x的右端点 r = n - 1;//右端点一定在【左端点，n-1】之间 while (l < r) { int mid = (l + r + 1) / 2; //因为写的是l=mid,所以需要补上1 if (q[mid] <= x) l = mid; else r = mid - 1; } cout << r << endl; } else cout << "-1 -1" << endl; } return 0; }
