162. 寻找峰值（Find Peak Element）

频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯/美团

题目

峰值元素指其值严格大于左右相邻值的元素。给定一个整数数组 nums（nums[-1] = nums[n] = -∞），找到任意一个峰值元素并返回其索引。要求 O(log n) 时间。

示例：

输入: nums = [1,2,3,1]
输出: 2 (索引 2，值 3 是峰值)

思路

二分：取中点 mid，比较 nums[mid] 和 nums[mid + 1]：

• nums[mid] > nums[mid + 1]：左侧存在峰值（包括 mid 本身），r = mid
• 否则：右侧存在峰值，l = mid + 1

保证每次缩小一半且不丢失答案。因为相邻值必然不相等（严格大于/小于），所以比较方向唯一确定。

边界条件 nums[-1] = nums[n] = -∞ 保证了数组两端天然是”谷底”，峰值必然存在。

代码

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid + 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

复杂度

• 时间：O(log n)
• 空间：O(1)

边界条件

• 长度 1：唯一元素就是峰值，循环不执行，直接返回 0
• 峰值在两端（单调递增/递减）：单调递增时 l 一路右推直到 r；单调递减时 r 一路左缩，都会收敛到端点
• 数组全部相同：题目保证相邻值不相等（严格大于/小于），不会出现

变式

• 852. 山脉数组的峰顶索引：数组先增后减，只有一个峰值，本题的特化版本
• 二维矩阵找峰值：先用二分找到列最大值，再向左右扩张，O(m log n) 或 O(n log m)

易错点

• 循环条件是 l < r 不是 l <= r，跳出后 l == r 就是答案，不需要再检查
• 比较对象是 nums[mid] 和 nums[mid + 1]，不是和 nums[mid - 1]，注意别越界
• 题目只要求返回任意一个峰值，不是全局最大（全局最大值必然也是峰值，但二分不保证找到它）

面试追问

• 为什么用二分能保证找到峰值？ 数组两端是负无穷，如果 nums[mid] < nums[mid+1]，说明右侧有上升趋势，至少能在右侧找到一个峰值；同理 nums[mid] > nums[mid+1] 左侧必有峰值。每次排除一半但绝不丢掉解——这就是二分正确性的核心
• 和普通二分的区别？ 普通二分靠 target 值决定方向，本题靠局部单调性（上升/下降趋势）决定方向，不依赖有序整体

关联题

• 同套路：153. 寻找旋转排序数组中的最小值 —— 同样利用局部有序性质二分
• 进阶：852. 山脉数组的峰顶索引 —— 本题特化版，同模板代码直接复用
• 知识点：二分查找模板见二分查找