【GESP】C++五级练习题 luogu-P2249 【深基13.例1】查找
GESP C++ 五级练习题，二分查找考点应用，重点理解二分查找和STL二分查找库的应用。五级考生可以练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。
luogu-P2249 【深基13.例1】查找
题目要求
题目描述
输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。
输入格式
第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。
第二行 $n$ 个整数，表示这些待查询的数字。
第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。
输出格式
输出一行，$m$ 个整数，以空格隔开，表示答案。
输入输出样例 #1
输入 #1
1
2
3
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出 #1
1
1 2 -1
说明/提示
数据保证，$1 \leq n \leq 10^6$，$0 \leq a_i,q \leq 10^9$，$1 \leq m \leq 10^5$
本题输入输出量较大，请使用较快的 IO 方式。
题目分析
1. 问题分析
本题的核心任务是在一个单调不减（即有序）的序列中，查找给定数字 $q$ 第一次出现的位置（编号）。如果找不到，输出 -1。
- 数据规模：序列长度 $n \le 10^6$，询问次数 $m \le 10^5$。
- 朴素做法：如果对于每次询问都从头遍历序列查找（线性查找），单次查询时间复杂度为 $O(n)$，总时间复杂度为 $O(n \times m) \approx 10^{11}$。这一计算量远超通常 1 秒（约 $10^8$ 次运算）的时间限制，会导致超时（TLE）。
- 优化算法：利用序列有序这一特性，我们可以使用二分查找算法。二分查找的单次查询时间复杂度为 $O(\log n)$。总时间复杂度为 $O(m \log n) \approx 10^5 \times 20 \approx 2 \times 10^6$，这是一个非常高效的算法，完全可以在时限内通过。
2. 解题思路
我们需要找到序列中第一个等于 $q$ 的元素的位置。这与普通的二分查找（只要找到一个相等甚至找 mid）略有不同，需要处理“第一个”这个要求。
方法一：手写二分查找
我们可以维护一个查找区间 $[l, r]$，并使用此时的中间位置 $mid$ 进行判断：
- 如果
nums[mid] < q：说明 $q$ 一定在 $mid$ 的右侧，更新 $l = mid + 1$。 - 如果
nums[mid] >= q：- 此时 $nums[mid]$ 可能是 $q$，也可能比 $q$ 大。
- 即使
nums[mid] == q，由于我们要找的是第一个出现的位置，可能左边还有等于 $q$ 的数。 - 因此，我们记录当前位置为可能的答案（
ans = mid，仅当相等时），并继续尝试向左侧区间收缩查找，更新 $r = mid - 1$。
- 循环结束后的
ans即为结果。初始化ans = -1，如果从未找到等于 $q$ 的数，则输出 -1。
方法二：使用 STL 的 lower_bound
我们在文章【GESP/CSP】编程武器库-5, 二分查找标准库(lower_bound/upper_bound)中刚刚介绍了C++ 标准库 <algorithm> 中提供了 std::lower_bound 函数，非常适合解决此类问题。
- 判断：
- 通过
lower_bound找到位置p。 - 首先检查
p是否越界（即是否等于last），如果越界说明所有数都比 $q$ 小，没找到。 - 其次检查
*p是否等于q。因为lower_bound返回的是 $\ge q$ 的第一个数，可能是 $q$ 也可能是比 $q$ 大的数。只有当*p == q时，才是找到了。
- 通过
- 计算下标：利用指针减法
p - nums即可得到对应的下标（注意数组的起始位置）。
示例代码
方法一、手写二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
int nums[1000005];
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
std::cin >> nums[i];
}
// 二分查找：寻找第一个等于 q 的位置
while (m--) {
int q;
std::cin >> q;
int ans = -1;
int l = 1, r = n; // 初始化左右边界
while (l <= r) {
int mid = l + (r - l) / 2; // 防止溢出的中间位置计算
if (nums[mid] < q) {
// 中间值小于目标值，说明目标在右半部分，且不包括 mid
l = mid + 1;
} else {
// nums[mid] >= q
if (nums[mid] == q) {
// 找到了一个等于 q 的值，记录位置
// 但我们要找的是 *第一个*，所以继续向左找
ans = mid;
}
// 即使找到了，也要向左收缩 r，尝试寻找更靠左的 q
// 或者 nums[mid] > q，也需要向左收缩
r = mid - 1;
}
}
std::cout << ans << " ";
}
return 0;
}
方法二、STL 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <algorithm>
#include <iostream>
#include <vector>
// P2249 【深基13.例1】查找 - STL版本实现
// 使用 std::lower_bound 快速查找第一个大于等于目标值的元素位置
int nums[1000005];
int main() {
// 优化输入输出效率
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
if (!(std::cin >> n >> m)) return 0;
for (int i = 1; i <= n; i++) {
std::cin >> nums[i];
}
while (m--) {
int q;
std::cin >> q;
// std::lower_bound 返回指向第一个 >= q 的元素的指针（或迭代器）
// 范围是 [nums + 1, nums + n + 1)
int* p = std::lower_bound(nums + 1, nums + n + 1, q);
// 检查是否找到：
// 1. p != nums + n + 1: 确保没有越界（即数组中存在 >= q 的数）
// 2. *p == q: 确保找到的数确实是 q（因为 lower_bound 也可能返回大于 q
// 的数）
if (p != nums + n + 1 && *p == q) {
// 计算下标：指针相减
std::cout << (p - nums) << " ";
} else {
// 没找到或者找到的是大于 q 的数
std::cout << -1 << " ";
}
}
std::cout << "\n";
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
