题目来源：改编自 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。

学习目标

• 在非递减序列上实现左右边界两次折半，分别定位目标值的首次与末次出现下标；
• 正确处理目标不存在（输出 -1 -1）、目标只出现在首末位置、整段重复等边界；
• 说明两次折半各自维持的循环不变量，以及每次查询 $O(\log n)$ 如何支撑 $2\times {10}^5$ 次查询。

前置知识与环境

先阅读第 8.1 节 基础查找与折半查找的"折半查找算法"与"判定树与比较次数"两节，掌握区间收缩的循环不变量；再对照该节"练习"第 4 题，思考边界更新方向改变时循环条件应如何配合。

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

任务

给定一个非递减的整数序列与若干查询值，对每个查询输出该值在序列中首次出现与末次出现的下标（下标从 1 开始，两个整数之间用空格分隔）；若序列中不存在该值，输出 -1 -1。

输入格式

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

输出格式

共 q 行，每行两个整数 p1 p2：该查询值首次与末次出现的下标（1 起）；不存在则输出 -1 -1。

数据范围与限制

项目	范围
序列长度 n	1 ≤ n ≤ 2×10⁵
查询次数 q	1 ≤ q ≤ 2×10⁵
序列元素	−10⁹ ≤ 元素 ≤ 10⁹，且非递减
查询值	−10⁹ ≤ t ≤ 10⁹（可能不存在于序列中）
时间复杂度要求	每次查询 $O(\log n)$；$O(nq)$ 顺序扫描会在压力用例超时
输出上限	8 MB（q 行逐行输出，判题器放宽了默认 1 MB 输出上限）

正常、边界与错误情况

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

样例

样例 1

8 5
1 2 4 4 4 7 8 8
4 8 1 0 9

3 5
7 8
1 1
-1 -1
-1 -1

序列中 4 出现在下标 3～5，8 出现在下标 7～8，1 只出现一次（首末相同，都是下标 1）；0 与 9 落在序列取值范围之外，不存在。

样例 2

1 3
42
-5 42 43

-1 -1
1 1
-1 -1

实现提示

分别写两个折半函数，循环不变量分别为"首次出现位置若存在，必在 [low, high] 内"与"末次出现位置若存在，必在 [low, high] 内"：

• 左边界：a[mid] >= key 时向左收缩并记录候选位置，a[mid] < key 时向右收缩；
• 右边界：a[mid] <= key 时向右收缩并记录候选位置，a[mid] > key 时向左收缩。

也可以统一写成"命中 a[mid] == key 时先记录、再继续向对应方向收缩"，这正是教材"练习"第 4 题边界更新训练的变体。查询不存在时左边界函数返回 -1，此时不必再做右边界折半。

运行

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

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

完成清单

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

思考与复盘

1. 若把"首末两次折半"合并成一次折半再加线性向两边扩散，最坏会退化到什么复杂度？构造一个使其退化的序列。
2. 折半查找要求非递减；如果序列递减，两个方向的比较应如何镜像修改？
3. 对比 lower_bound/upper_bound 风格（左闭右开区间）与课程风格的闭区间写法，两者的循环不变量与结束状态有何对应关系？