题目来源：改编自洛谷 P2249【深基13.例1】查找。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。

学习目标

• 在非递减序列上实现返回首次出现位置的折半查找，而不是任意命中位置；
• 正确处理查找失败（输出 -1）与目标落在序列两端之外的边界；
• 解释为什么折半查找要求顺序存储与有序前提，以及 $O(\log n)$ 如何支撑 $2\times {10}^5$ 次查询。

前置知识与环境

先阅读第 8.1 节 基础查找与折半查找的"折半查找算法"与"判定树与比较次数"两节，掌握区间收缩的循环不变量。

在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。

任务

给定一个非递减的整数序列，对每个查询值输出它在序列中第一次出现的下标（下标从 1 开始）；若序列中不存在该值，输出 -1。

输入格式

• 第一行：两个整数 n 和 m，分别为序列长度与查询次数；
• 第二行：n 个按非递减顺序排列的整数；
• 第三行：m 个整数，表示依次查询的值。

输出格式

共 m 行，每行一个整数：该查询值首次出现的下标（1 起），不存在则输出 -1。

数据范围与限制

项目	范围
序列长度 n	1 ≤ n ≤ 2×10⁵
查询次数 m	1 ≤ m ≤ 2×10⁵
序列元素	0 ≤ 元素 ≤ 10⁹
查询值	−10⁹ ≤ q ≤ 10⁹（允许不在序列取值范围内）
时间复杂度要求	每次查询 $O(\log n)$；$O(nm)$ 顺序扫描会在压力用例超时
输出上限	8 MB（m 行逐行输出，判题器放宽了默认 1 MB 输出上限）

正常、边界与错误情况

• 正常：目标存在且出现多次时必须返回第一个下标；
• 边界：目标等于首元素、末元素；目标小于全部元素或大于全部元素；n = 1；
• 查询越界：查询值允许为负或大于 10⁹，仍按"不存在"处理，输出 -1。

样例

样例 1

11 5
1 3 3 3 5 7 9 9 11 13 15
3 9 4 15 16

2
7
-1
11
-1

序列中 3 出现在下标 2～4，首次出现是 2；9 出现在下标 7～8，首次出现是 7；4 不存在；15 在末尾下标 11；16 超出最大值，不存在。

样例 2

1 3
42
-5 42 43

-1
1
-1

实现提示

用"左边界"折半：循环不变量为答案落在 [low, high]，mid = low + (high - low) / 2，a[mid] >= q 时向左收缩并记录候选位置，a[mid] < q 时向右收缩。结束后核对记录位置上的值是否等于 q。

直接在命中 a[mid] == q 时返回，得到的是某个命中位置而非首次出现位置，遇到重复值会错。

运行

make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-08/exercise/E-08-02-binary-search-first-index

需要单用例或严格评分时使用 make run CASE=005-stress-2e5 与 make score；也可用 pnpm lab:score -- labs/chapter-08/exercise/E-08-02-binary-search-first-index 兜底。

完成清单

• 样例 1、样例 2 与 make run 全部用例通过；
• 重复值返回的是首次出现下标，而不是任意命中下标；
• 查询值越界（负数、大于 10⁹）时输出 -1 而不是数组越界或死循环；
• 压力用例（n = m = 2×10⁵）在时限内完成，能说明折半查找的比较次数约为 $\lceil {\log }_2(n+1)\rceil$。

思考与复盘

1. 如果序列是递减的，循环中两次比较方向如何调整？折半查找的前提还剩哪些？
2. 折半查找在链式存储上为什么不成立？瓶颈发生在哪一步？
3. 对比顺序查找：当 m 次查询都在同一张表上进行时，"先排序再折半"的预处理成本何时能被摊还？