你好，同学。我是你的教练。今天我们要学习的是算法竞赛中最基础、也是最重要的算法之一：二分查找（Binary Search）。

虽然这道题看起来简单，但它是你理解“单调性”和“对数复杂度”的起点。在 NOI 竞赛中，许多复杂的题目（如二分答案、分数规划）最终都会归结为这个基础逻辑。请拿出草稿纸，随我一起进入思考过程。

一、 思路提示（不含完整解答）

1. 核心前提：二分查找必须在有序序列上进行。题目给出的数组已经是升序排列，这是使用二分的绿灯信号。
2. 核心思想：通过每次检查区间的中点，将搜索范围缩小一半。
3. 区间选择：常用的做法是维护一个“左闭右闭”的区间 [left, right]。
   • 如果中点值刚好等于目标值，任务完成。
   • 如果中点值大于目标值，说明目标在左半部分。
   • 如果中点值小于目标值，说明目标在右半部分。

二、 预备知识点

1. 单调性：序列必须是有序的（升序或降序）。
2. 双指针法：使用两个变量维护当前的搜索边界。
3. 时间复杂度分析：理解为什么每次折半的操作会导致 $O(\log n)$ 的效率。
4. 防止整数溢出：在计算中点时，left + (right - left) / 2 比 (left + right) / 2 更稳健。

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

请在你的草稿纸上跟我一起画：

场景模拟：数组 [-1, 0, 3, 5, 9, 12]，查找 target = 9。

1. 初始化：
   • 画一条线段代表数组。
   • left 指向 0（元素 -1），right 指向 5（元素 12）。
2. 第一次迭代：
   • 计算中点 mid = (0 + 5) / 2 = 2。
   • 看下标 2 的元素是 3。
   • 因为 3 小于 9，所以 9 肯定在 3 的右边。
   • 动作：把 left 挪到 mid + 1 = 3 的位置。现在的区间变成 [3, 5]。
3. 第二次迭代：
   • 计算新中点 mid = (3 + 5) / 2 = 4。
   • 看下标 4 的元素是 9。
   • 找到目标！返回下标 4。

思考：如果你查找的是 2，最后 left 和 right 会发生什么冲突？（当 left > right 时，说明区间为空，查找失败）。

四、 题目描述 (NOI 风格)

题目名称：二分查找 (binary_search) 输入文件：binary_search.in 输出文件：binary_search.out

【问题描述】 给定一个 $n$ 个元素有序的（升序）整型数组 nums 和一个目标值 target。写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

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

【输出格式】 输出一个整数，表示目标值的索引；若不存在则输出 -1。

【样例 1 输入】

6 9
-1 0 3 5 9 12

【样例 1 输出】

4

【样例 1 说明】 9 出现在 nums 中并且下标为 4。

【样例 2 输入】

6 2
-1 0 3 5 9 12

【样例 2 输出】

-1

【样例 2 说明】 2 不存在于 nums 中因此返回 -1。

【数据范围限制】

• $1 \le n \le 10^4$
• 数组中每个元素均在 $[-9999, 9999]$ 之间。
• nums 中的所有元素是不重复的。
• nums 按照升序排列。

五、 算法思路流程图 (C++ 14 风格逻辑)

为了兼容 Mermaid 语法，特殊符号已转换：

graph TD
    Start(开始) --> Init(初始化 L 等于 0, R 等于 n 减 1)
    Init --> Loop{L 小于等于 R}
    Loop -- 否 --> ReturnFail(返回负 1)
    Loop -- 是 --> CalcMid(计算 Mid 等于 L 加 -R 减 L- 除以 2)
    CalcMid --> Check{nums-at-Mid 关系}
    
    Check -- 等于 Target --> ReturnSuccess(返回 Mid)
    Check -- 大于 Target --> MoveR(R 更新为 Mid 减 1)
    Check -- 小于 Target --> MoveL(L 更新为 Mid 加 1)
    
    MoveR --> Loop
    MoveL --> Loop
    ReturnSuccess --> End(结束)
    ReturnFail --> End

六、 复杂度分析思考

1. 时间复杂度分析：

   • 初始区间大小为 $n$。
   • 每次操作后区间变为原来的 $1/2$。
   • 设经过 $k$ 次操作区间缩减为 1，则 $n \cdot (1/2)^k = 1$，得 $k = \log_2 n$。
   • 结论：时间复杂度为 $O(\log n)$。在 $n=10^4$ 时，最多只需要 14 次比较。

2. 空间复杂度分析：

   • 我们只使用了常数个变量（L, R, Mid），因此空间复杂度为 $O(1)$。

3. 时间复杂度优化建议：

   • 对于这种基础二分，目前的复杂度已经是理论最优。
   • 在 NOI 比赛中，若 $n$ 达到 $10^7$ 级别，需要注意 scanf 或快读的读入优化，因为 $O(\log n)$ 非常快，瓶颈往往在 I/O 上。

七、 总结：读题时的关键词在哪里？

当你读到一道题，出现以下关键词时，一定要在草稿纸上写下“二分”：

1. “有序” (Sorted)：这是二分的入场券。
2. “升序/降序” (Non-decreasing/Non-increasing)：同上。
3. “时间复杂度 $O(\log n)$”：这是题目对你的强制暗示。
4. “查找目标值”：基础二分。
5. “最大值最小”或“最小值最大”：这是进阶的“二分答案”关键词。

同学，理清思路了吗？现在请在草稿纸上尝试写出伪代码，注意 while 循环的退出条件。加油！