寻找峰值 · 无序数组上的坡度二分

坡度追踪 · 非有序二分

把数组看成山脉折线，边界外视为 -∞。只比较 nums[mid] 与 nums[mid+1] 的坡度，每次丢掉不可能含峰的一半。

当前输入

nums = [1, 2, 3, 1]

主样例，峰在下标 2（值 3）

算法返回峰

下标 2

时间 O(log n)

空间 O(1)

折线边界坡度收敛总结

Step 1/9 · ① 山脉折线

Scene 1：把数组读成山脉折线

当前发生了什么

Scene 1：把数组读成山脉折线

峰值不要求全局最大，只需严格大于左右邻居。数组可以无序、可以有多个峰——题目保证至少存在一个。这不是有序数组二分，而是在折线上用局部坡度决定往哪半边收缩。

为什么这一步是对的

把 nums 连成折线后，每个元素的高度就是「海拔」。峰是局部最高点，比较的是相邻两点的升降，而非与 target 对齐。

执行表

步	lo	hi	mid	坡度	操作
1	0	3	1	2 < 3	lo=2
2	2	3	2	3 ≥ 1	hi=2

坡度追踪舞台

nums=[1,2,3,1] · 找任一峰值下标

代码同步 · Go

① 山脉折线

1func findPeakElement(nums []int) int {
2    lo, hi := 0, len(nums)-1
3 
4    for lo < hi {
5        mid := lo + (hi-lo)/2
6 
7        if nums[mid] < nums[mid+1] {
8            lo = mid + 1
9        } else {
10            hi = mid
11        }
12    }
13 
14    return lo
15}

本步不变量

整段 [0, n-1] 在虚拟边界 -∞ 之间，必含至少一个峰。

剧本时间线 · 共 9 步

循环不变量

1.[lo, hi] 区间内始终至少存在一个峰值（边界 nums[-1]、nums[n] 视为 -∞）。
2.每步只比较 nums[mid] 与 nums[mid+1]，用局部坡度决定丢弃哪一半。
3.循环条件必须是 lo < hi：循环体内访问 mid+1，lo==hi 时 mid+1 会越界。
4.当 lo == hi 时收敛，直接返回 lo（不必再比较邻居）。

面试 · 一段话讲清楚

这题不是找最大值，也不是有序数组二分。我们利用峰值一定存在，以及局部坡度判断方向。若 nums[mid] < nums[mid+1]，说明右侧沿上坡方向一定能遇到峰；否则左侧含 mid 一定有峰。每次缩小一半区间，时间 O(log n)，空间 O(1)。

常见错误

错误 1：当成有序数组二分
数组可以任意波动，没有全局单调性；靠的是「上坡必遇峰」而非 target 比较。
错误 2：循环写成 lo <= hi
每次迭代要读 nums[mid+1]。若 lo==hi 仍进入循环，mid+1 越界。应 lo<hi，收敛后 return lo。
错误 3：上坡时写 hi = mid 或 lo = mid
nums[mid] < nums[mid+1] 说明 mid 本身不是峰（右侧更高），峰至少在 mid+1，故 lo = mid+1。