【洛谷 P2249】查找（深基 13. 例 1）+ 详细分析
题目链接
- 洛谷 P2249 查找
一、题目简介
题目描述
输入 n 个不超过 (10^9) 的单调不减非负整数 (a_1,a_2,\dots,a_n)，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到则输出 (-1)。
输入格式
- 第一行：两个整数 n 和 m，表示数字个数和询问次数。
- 第二行：n 个整数，表示待查询的序列（单调不减）。
- 第三行：m 个整数，表示每次查询的 q。
输出格式
输出一行，m 个整数，以空格隔开，表示每次查询的答案（从 1 开始编号）。
输入输出样例
输入
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出
1 2 -1
数据范围与提示
- (1 \le n \le 10^6)
- (0 \le a_i,q \le 10^9)
- (1 \le m \le 10^5)
本题输入输出量较大，请使用较快的 IO 方式（如 scanf/printf）。
二、解题思路详细分析
1、问题难点
- 数据规模极大：n 高达 (10^6)，m 高达 (10^5)，如果使用暴力遍历（(O(n)) 单次查询），总时间复杂度 (O(n \times m) = 10^{11})，会严重超时。
- 要求找第一次出现的位置：普通的 binary_search 只能判断是否存在，无法直接返回首次出现的下标。
- 序列是单调不减的：这是使用二分查找的关键前提。
2、核心算法：二分查找（找左边界）
本题的核心是二分查找的左边界模板，专门用于在有序序列中找到第一个大于等于目标值的位置。
核心原理
对于单调不减的序列，我们要找 q 第一次出现的位置，等价于找第一个满足 a[i] >= q 的位置 i，再验证 a[i] == q：
- 如果 a[i] == q，说明找到了，返回 i；
- 如果 a[i] != q，说明序列中不存在 q，返回 -1。
二分边界模板
int l = 0, r = n + 1;
while(l + 1 < r) {int mid = l + r >> 1;if(a[mid] >= q) r = mid;else l = mid;
}
return a[r] == q ? r : -1;
- 初始边界 l=0, r=n+1：覆盖所有可能的下标（数组下标从 1 到 n）。
- 循环条件 l+1 < r：当 l 和 r 相邻时停止，此时 r 就是第一个满足条件的位置。
- 更新规则：a[mid] >= q 时，答案可能在左半部分，所以 r=mid；否则答案在右半部分，l=mid。
3、图文逻辑演示
以样例 a = [1,3,3,3,5,7,9,11,13,15,15]，查询 q=3 为例：
- 初始：l=0, r=12
- 第一次：mid=(0+12)/2=6，a[6]=7 >= 3 → r=6
- 第二次：mid=(0+6)/2=3，a[3]=3 >= 3 → r=3
- 第三次：mid=(0+3)/2=1，a[1]=1 < 3 → l=1
- 第四次：mid=(1+3)/2=2，a[2]=3 >= 3 → r=2
此时 l+1 = r，循环结束，r=2，验证 a[2]=3，返回 2，即首次出现位置。
4、时间复杂度分析
- 预处理：(O(n)) 读取数组
- 单次查询：(O(\log n))，m 次查询总时间 (O(m \log n))
- 整体复杂度：(O(n + m \log n))，对于 (n=106)、(m=105)，完全可以在时间限制内通过。
三、AC 代码（超详细注释）
#include <bits/stdc++.h>
using namespace std;// 数组最大长度：1e6+5，满足题目n≤1e6的要求
const int N = 1e6 + 5;
int n, m, q, a[N];// 二分查找：找q第一次出现的位置
int find(int q) {// 边界：l初始为0，r为n+1（覆盖1~n的所有下标）int l = 0, r = n + 1;// 循环条件：l和r不相邻时继续while (l + 1 < r) {// 计算中间位置，等价于(l + r) / 2，位运算效率更高int mid = l + r >> 1;// 关键判断：a[mid] >= q时，答案在左半部分，收缩右边界if (a[mid] >= q)r = mid;elsel = mid;}// 循环结束后r是第一个>=q的位置，验证是否等于qreturn a[r] == q ? r : -1;
}int main() {// 读取n和mcin >> n >> m;// 读取序列，数组下标从1开始（和题目编号对应）for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}// 处理m次查询for (int i = 1; i <= m; i++) {scanf("%d", &q);// 调用二分查找并输出结果printf("%d ", find(q));}return 0;
}
四、代码核心细节讲解
1、数组下标设计
- 数组 a[N] 下标从 1 开始，和题目中 “从 1 开始编号” 的要求直接对应，避免了后续输出时的 +1 操作，减少出错概率。
- 初始边界 l=0, r=n+1，是为了覆盖所有可能的下标，即使 q 比所有元素都大，r 也会停在 n+1，此时 a[r] 越界？不，因为 n 是数组长度，a 定义为 1e6+5，r=n+1 不会越界（且此时 a[r] 为初始值 0，不等于 q，返回 -1）。
2、IO 优化
- 题目提示 “输入输出量较大”，所以使用 scanf/printf 代替 cin/cout：
- cin/cout 默认同步 stdio，速度较慢，大量数据时容易超时；
- scanf/printf 是 C 标准输入输出，效率更高，适合大数据场景。
3、二分边界的关键
- 循环条件 l + 1 < r 是左边界二分的经典写法，避免了死循环问题。
- 每次更新时，r=mid 是关键，它保证了即使 a[mid] == q，也会继续向左收缩，找到更靠左的位置，也就是第一次出现的位置。
4、边界情况处理
- 当 q 比所有元素都小时：循环结束后 r=1，验证 a[1] == q 则返回 1，否则返回 -1。
- 当 q 比所有元素都大时：循环结束后 r=n+1，a[r] 为 0，不等于 q，返回 -1。
- 当 q 不存在于序列中时：返回 -1，符合题目要求。
五、总结
本题是二分查找左边界模板的经典应用，核心要点：
- 利用序列的单调性，将暴力的 (O(n)) 优化为 (O(\log n))；
- 掌握左边界二分模板，找到第一个大于等于目标值的位置；
- 注意大数据量下的 IO 优化，使用 scanf/printf；
- 数组下标和边界设计要和题目要求对齐，避免额外的下标转换错误。
这个模板可以直接复用在所有 “有序序列中找元素第一次出现位置” 的场景中，是算法竞赛中非常高频的考点。