你好，同学。我是你的 OI 教练。今天我们要攻克的是一道非常巧妙的题目——寻找峰值。

在 NOI 竞赛中，二分查找通常用于有序数组，但这道题证明了：只要问题具备“二段性”或“局部单调性”，即便数组无序，我们依然可以用 $O(\log n)$ 的降维打击来解决。

一、 预备知识点

1. 二分查找（Binary Search）：跳出“只能在有序数组使用”的思维定式。
2. 局部单调性：理解为什么通过比较相邻元素就能判定峰值的方向。
3. 边界处理：处理 $nums[-1] = nums[n] = -\infty$ 的隐含条件。
4. 时间复杂度分析：对数级别复杂度 $O(\log n)$ 的推导。

二、 题目描述 (NOI 风格)

题目名称：寻找峰值 (peak) 输入文件：peak.in 输出文件：peak.out

【问题描述】 峰值元素是指其值严格大于左右相邻元素的元素。 给定一个长度为 $n$ 的整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。这意味着对于数组边界元素，只需与其唯一的相邻元素比较。 你必须设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题。

【输入格式】 第一行包含一个整数 $n$，表示数组长度。 第二行包含 $n$ 个由空格隔开的整数，表示数组 nums。

【输出格式】 输出一个整数，表示任何一个峰值元素的索引（下标从 0 开始）。

【样例 1 输入】

4
1 2 3 1

【样例 1 输出】

2

【样例 1 说明】 3 是峰值元素，它的左侧是 2，右侧是 1。索引为 2。

【样例 2 输入】

7
1 2 1 3 5 6 4

【样例 2 输出】

5

【样例 2 说明】 你的函数可以返回索引 1（其峰值为 2）或者索引 5（其峰值为 6）。

【数据范围限制】

• $1 \le n \le 10^5$
• $-2^{31} \le nums[i] \le 2^{31} - 1$
• 对于所有有效的 $i$，都有 $nums[i] \neq nums[i + 1]$

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

请拿出草稿纸，随我画出这个逻辑。

1. 直觉分析：爬山法则

想象你在一条山脉上，由于两端都是无限深渊（$-\infty$），你只要往“高处”走，最终一定能遇到一个山峰。

2. 关键判定：中点 $mid$ 的处境

我们在数组中间取一个点 $mid$，把它和它的右邻居 $mid+1$ 比较：

• 情况 A：$nums[mid] < nums[mid+1]$
  • 说明“上坡”方向在右边。因为右边最终会遇到 $-\infty$，所以在右侧区间 $[mid+1, n-1]$ 必然存在一个峰值。
• 情况 B：$nums[mid] > nums[mid+1]$
  • 说明此时处于“下坡”或者已经在峰顶。左侧（包含 $mid$ 自己）一定存在峰值。

3. 为什么能二分？

尽管整个数组不是有序的，但通过比较 $mid$ 与 $mid+1$，我们可以确定性地排除掉一半的区间。这就是二分的核心。

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

为了防止 Mermaid 渲染错误，我们使用描述性文字代替特殊字符：

graph TD
    Start(开始) --> Init(初始化左边界 L 等于 0, 右边界 R 等于 n 减 1)
    Init --> Condition{L 小于 R}
    
    Condition -- 成立 --> CalcMid(计算 Mid 等于 L 加上 -R 减 L 的一半)
    CalcMid --> Compare{Mid 位置的值是否大于其右侧相邻值}
    
    Compare -- 是 --> MoveR(说明左侧包含 Mid 可能是峰值, 令 R 等于 Mid)
    Compare -- 否 --> MoveL(说明右侧必有更高处, 令 L 等于 Mid 加 1)
    
    MoveR --> Condition
    MoveL --> Condition
    
    Condition -- 不成立 --> Final(此时 L 等于 R, 即为峰值索引)
    Final --> End(输出 L 并结束)

五、 复杂度分析与建议

1. 时间复杂度思考过程：

   • 我们每一次比较（$O(1)$），都将搜索范围减少了一半。
   • 设数组长度为 $N$，经过 $k$ 次查找，范围缩小到 1。则 $2^k = N$，即 $k = \log_2 N$。
   • 结论：$O(\log N)$。对于 $N=10^5$，大约只需 17 次比较，效率极高。

2. 空间复杂度：

   • 迭代法仅需常数级额外空间，复杂度 $O(1)$。

3. 优化与陷阱（教练提示）：

   • 整型溢出：本题 $nums[i]$ 可能达到 int 极限。虽然比较本身没问题，但计算 mid 建议用 L + (R - L) / 2。
   • 边界访问：注意在 mid 比较时，mid+1 是否会越界？在 while (L < R) 逻辑下，mid 永远小于 R，所以 mid+1 是安全的。
   • 数据规模：NOI 比赛中如果 $N$ 很大且有时限要求，务必首选二分而非线性扫描。

六、 总结：读题关键词

在面对 NOI 级别的题目时，学会抓关键词：

1. “$O(\log n)$ 复杂度”：这是最直观的暗示，必须联想到二分查找或位运算相关数据结构。
2. “任何一个……即可”：这意味着题目不要求全局最优或唯一解，寻找“局部性质”通常是二分的切入点。
3. “相邻元素不相等”：这个条件非常重要，它保证了在任何一点都有明确的“上坡”或“下坡”方向，避免了平原导致二分失效。
4. 边界定义为 $-\infty$：这意味着只要数组不为空，峰值必然存在。

同学，理清思路了吗？现在尝试在草稿纸上模拟一次 [1, 2, 1, 3, 5, 6, 4] 的二分过程，然后准备编写你的代码。加油！