给定一个按照升序排列的长度为 nn 的整数数组,以及 qq 个查询。
对于每个查询,返回一个元素 kk 的起始位置和终止位置(位置从 00 开始计数)。
如果数组中不存在该元素,则返回 -1 -1
。
输入格式
第一行包含整数 nn 和 qq,表示数组长度和询问个数。
第二行包含 nn 个整数(均在 1∼100001∼10000 范围内),表示完整数组。
接下来 qq 行,每行包含一个整数 kk,表示一个询问元素。
输出格式
共 qq 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例:
6 3 1 2 2 3 3 4 3 4 5
输出样例:
3 4 5 5 -1 -1
#include <iostream> using namespace std; const int N = 100010; int n, m, temp, a[N]; int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; while (m--) { // temp 为要查找的值 cin >> temp; // 定义边界 int l = 0, r = n - 1; while (l < r) { // 做法第 1 步: A: 找中间值 int mid = l + r >> 1; // 做法第 1 步: B: 判断 if (a[mid] >= temp) r = mid; else l = mid + 1; } // 如果二分出来的值不等于要找的值,说明不存在 if (a[r] != temp) cout << "-1 -1" << endl; else { // 输出左边界 cout << l<< " "; l = 0, r = n - 1; while (l < r) { // 做法第 2 步: A: 找中间值 int mid = l + r + 1 >> 1; // 做法第 2 步: B: 判断 if (a[mid] <= temp) l = mid; else r = mid - 1; } cout << r << endl; } } return 0; }