你好，同学。我是你的教练。今天我们要讨论的题目是二分搜索进阶应用中的经典模型——在排序数组中查找元素的第一个和最后一个位置。

在 NOI 竞赛中，简单的二分查找通常只是工具，而能够灵活控制二分边界以锁定“一段等值区间的左右端点”才是真正的考点。

---

一、 预备知识点

1. 基础二分查找（Binary Search）：理解 $O(\log n)$ 的检索原理。
2. 左边界/右边界二分（Boundary Search）：当数组中存在重复元素时，如何精准定位起始和结束位置。
3. C++ STL 关联函数：了解 std::lower_bound 和 std::upper_bound 的底层逻辑（虽然 NOI 建议手写以应对变体）。

---

二、 题目描述 (NOI 风格)

题目名称：在排序数组中查找元素的第一个和最后一个位置 (search_range) 输入文件：search_range.in 输出文件：search_range.out

【问题描述】 给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，输出 -1 -1。 你必须设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题。

【输入格式】 第一行包含两个整数 $n$ 和 $target$，分别表示数组长度和目标值。 第二行包含 $n$ 个由空格隔开的整数，表示数组 nums。

【输出格式】 输出两个整数，由空格隔开，表示起始位置和结束位置的下标（下标从 0 开始）。

【样例 1 输入】

6 8
5 7 7 8 8 10

【样例 1 输出】

3 4

【样例 2 输入】

6 6
5 7 7 8 8 10

【样例 2 输出】

-1 -1

【样例 3 输入】

0 0

【样例 3 输出】

-1 -1

【数据范围限制】

• $0 \le n \le 10^5$
• $-10^9 \le nums[i], target \le 10^9$
• $nums$ 是一个非递减数组

---

三 : 启发式引导：草稿纸上的推演过程

请拿出你的草稿纸，我们以样例 1 [5, 7, 7, 8, 8, 10], target=8 为例：

第一步：常规二分的局限

当你用标准二分查找到一个 8（下标为 3 或 4）时，算法通常就结束了。但我们需要知道**“最左边的 8”和“最右边的 8”**。

第二步：寻找左边界的策略

1. 即便 nums[mid] == 8，我们也不停止。因为左边可能还有 8。
2. 收缩右边界：令 right = mid - 1，继续在左半部分找。
3. 用一个变量 ans 记录下当前看到的这个 8 的位置，然后继续压迫边界。

第三步：寻找右边界的策略

1. 同理，即便 nums[mid] == 8，我们也令 left = mid + 1，去右半部分探索。

第四步：空数组与不存在的情况

• 若 $n=0$，直接输出 -1 -1。
• 若二分结束后 ans 没被更新，说明没找到。

---

四、 算法思路流程图 (C++ 伪代码逻辑)

在 Mermaid 语法中，我们使用文字描述避开特殊字符：

graph TD
    Start(开始) --> Read(读取 n 和 target)
    Read --> CheckEmpty{n 是否等于 0}
    CheckEmpty -- 是 --> PrintFail(输出 -1 -1)
    CheckEmpty -- 否 --> FindLeft(寻找左边界)
    
    subgraph 寻找左边界逻辑
    L1(Left=0, Right=n-1, ansL=-1) --> W1{Left 小于等于 Right}
    W1 -- 是 --> M1(Mid 等于 Left 与 Right 的中间值)
    M1 --> C1{nums-Mid 是否大于等于 target}
    C1 -- 是 --> R1(ansL 记录 Mid, Right 等于 Mid 减 1)
    C1 -- 否 --> R2(Left 等于 Mid 加 1)
    R1 --> W1
    R2 --> W1
    end

    FindLeft --> FindRight(寻找右边界)

    subgraph 寻找右边界逻辑
    L2(Left=0, Right=n-1, ansR=-1) --> W2{Left 小于等于 Right}
    W2 -- 是 --> M2(Mid 等于 Left 与 Right 的中间值)
    M2 --> C2{nums-Mid 是否小于等于 target}
    C2 -- 是 --> R3(ansR 记录 Mid, Left 等于 Mid 加 1)
    C2 -- 否 --> R4(Right 等于 Mid 减 1)
    R3 --> W2
    R4 --> W2
    end

    FindRight --> FinalCheck{ansL 且 ansR 对应的值是否为 target}
    FinalCheck -- 否 --> PrintFail
    FinalCheck -- 是 --> PrintAns(输出 ansL 和 ansR)

---

五、 复杂度分析与优化建议

1. 时间复杂度分析

• 过程：进行了两次独立的二分查找。
• 计算：$O(\log n) + O(\log n) = O(\log n)$。
• 思考：对于 $N=10^5$ 的数据，$\log N \approx 17$，总计算次数约 34 次，远超题目要求。

2. 空间复杂度分析

• 计算：只需常数级别的辅助变量，复杂度 $O(1)$（不计输入数组）。

3. 优化建议

• STL 替代：在 NOI 中，你可以使用 lower_bound 找第一个 $\ge target$ 的位置，使用 upper_bound 找第一个 $> target$ 的位置。但要注意，upper_bound 返回的位置减 1 才是目标值的右边界。
• 边界判断：在获取 ansL 后，如果 nums[ansL] != target，说明数组中根本没有这个数，可以直接输出 -1 -1，不需要再进行第二次二分。

---

六、 总结：读题时的关键词

在 NOI 题目中，看到以下关键词要保持敏感：

1. “排序数组” / “非递减顺序”：这是使用二分查找的绝对前提。
2. “时间复杂度 $O(\log n)$”：这几乎是在明示你必须使用二分，不能进行 $O(n)$ 的线性扫描（虽然 $10^5$ 线性扫描在 1s 内能过，但在更高难度的题或大数据量下会超时）。
3. “第一个位置”和“最后一个位置”：这要求你的二分逻辑不能在 nums[mid] == target 时立即返回，而是要继续向两侧逼近。

同学，你可以在草稿纸上试着手写一下这两个稍有不同的二分函数吗？注意 left 和 right 的更新条件。加油！