你好，同学！我是你的 OI 教练。今天我们要攻克的是二分搜索（Binary Search）中最基础但也最容易在边界条件上“翻车”的经典题型。

在 NOI 竞赛中，这属于“基础算法”范畴，但它是构建复杂算法（如二分答案、树状数组上二分等）的基石。请拿出草稿纸，随我一起拆解。

---

一、 预备知识点

1. 二分查找（Binary Search）：处理具有单调性序列的高效检索方法。
2. 左闭右闭区间逻辑：掌握 [left, right] 定义下的循环终止条件与边界收缩。
3. Lower Bound（下界检索）：理解如何寻找序列中第一个“大于或等于”目标值的元素位置。

---

二、 题目描述 (NOI 风格)

题目名称：搜索插入位置 (search_insert) 输入文件：search_insert.in 输出文件：search_insert.out

【问题描述】 给定一个排序数组 nums（无重复元素）和一个目标值 target。

1. 如果目标值存在，返回其下标。
2. 如果目标值不存在，返回它将会被按顺序插入的位置。 你必须设计并实现时间复杂度为 $O(\log n)$ 的算法。

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

【输出格式】 输出一个整数，表示目标值的索引或插入位置。

【样例 1 输入】

4 5
1 3 5 6

【样例 1 输出】

2

【样例 2 输入】

4 2
1 3 5 6

【样例 2 输出】

1

【样例 3 输入】

4 7
1 3 5 6

【样例 3 输出】

4

【数据范围限制】

• $1 \le n \le 10^4$
• $-10^4 \le nums[i], target \le 10^4$
• $nums$ 为无重复元素的升序排列数组。

---

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

请在草稿纸上模拟 样例 2：nums = {1, 3, 5, 6}, target = 2。

第一步：确定搜索区间

我们使用最稳妥的“左闭右闭”区间：left = 0, right = n - 1。

第二步：迭代追踪

1. 第 1 次迭代：
   • mid = (0 + 3) / 2 = 1。
   • nums[1] 是 3。由于 3 大于 2，说明 2 如果存在，一定在左边。
   • 更新 right = mid - 1 = 0。
2. 第 2 次迭代：
   • mid = (0 + 0) / 2 = 0。
   • nums[0] 是 1。由于 1 小于 2，说明 2 如果存在，一定在右边。
   • 更新 left = mid + 1 = 1。
3. 终止判断：
   • 此时 left = 1, right = 0。满足 left > right，循环结束。

第三步：观察规律

观察此时 left 的值。在循环结束时，left 刚好指向了第一个大于 2 的元素（即 3）所在的位置，也就是我们要插入的位置。

思考题：

• 如果 target 比数组所有元素都大（样例 3），最后 left 会指向哪里？
• 如果数组中正好有 target，二分查找的分支该如何处理？

---

四、 复杂度分析思考

• 时间复杂度：

  • 由于每次比较后，搜索区间都会缩小一半（$N \rightarrow N/2 \rightarrow N/4 \dots$）。
  • 总共需要的步数为 $\log_2 N$。对于 $N=10^4$，大约只需要 14 次比较。
  • 优化建议：在计算 mid 时，为了防止 left + right 溢出（虽然本题数据范围较小），建议使用 mid = left + (right - left) / 2。

• 空间复杂度：

  • 算法只使用了常数个辅助变量（left, right, mid），故为 $O(1)$。

---

五、 算法思路流程图 (Mermaid 格式)

graph TD
    A(开始) --> B(初始化 left 等于 0, right 等于 n 减 1)
    B --> C{left 小于等于 right}
    C -- 否 --> D(输出 left 并结束)
    C -- 是 --> E(计算 mid 等于 left 加-right减left-除以2)
    E --> F{nums-mid 等于 target}
    F -- 是 --> G(输出 mid 并结束)
    F -- 否 --> H{nums-mid 小于 target}
    H -- 是 --> I(left 更新为 mid 加 1)
    H -- 否 --> J(right 更新为 mid 减 1)
    I --> C
    J --> C

---

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

在 NOI 考试中，看到以下关键词要立刻联想到二分：

1. “排序数组” / “升序排列”：这是使用二分查找的先决条件。
2. “时间复杂度 $O(\log n)$”：这是强制要求，暗示你绝对不能使用 $O(n)$ 的线性遍历，否则在大数据量下会超时（TLE）。
3. “插入位置”：这实际上是在考察二分查找的变体。当找不到目标时，需要明确二分边界变量（left 或 right）在退出循环时的最终含义。

同学，理清了 left 和 right 的变动轨迹，这类题就再也不会写错边界了。去尝试实现它吧！