寻找峰值：二分在非有序数组上的抽象应用

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 16 分钟 | 难度：⭐⭐⭐

---

开篇故事

LeetCode 162 是我做过的最有意思的二分查找题之一，因为它完全推翻了我对"二分查找需要有序数组"的认知。

我第一次看到这道题时，第一反应是：数组完全无序，怎么可能用二分？直接线性扫描不就行了吗？

后来我仔细读了题目要求：O(log n) 的时间复杂度。好，那必须用二分了。但问题是，无序数组用二分，判断条件是什么？

冥思苦想了一会儿，我突然想通了一件事：峰值不需要全局最大值，任意一个局部极大值就行。这意味着，只要我能判断"朝哪个方向走，肯定能遇到峰值"，我就能用二分。

比较 nums[mid] 和 nums[mid+1]：

• 如果 nums[mid] < nums[mid+1]，说明 mid 处在上升沿，右侧某处必有峰值。
• 如果 nums[mid] > nums[mid+1]，说明 mid 处在下降沿，左侧（含 mid）某处必有峰值。

这就是二分查找最抽象的应用：不是在数组里搜索一个值，而是用"方向性判断"来引导搜索。

---

一、题目解析

题目（LeetCode 162）： 给定整数数组 nums，找到峰值元素并返回其下标。峰值元素是指其值严格大于左右相邻值的元素。可以假设 nums[-1] = nums[n] = -∞（边界外都是负无穷）。如果数组含多个峰值，返回任意一个即可。要求 O(log n)。

示例：

• 输入：nums = [1,2,3,1]，输出：2
• 输入：nums = [1,2,1,3,5,6,4]，输出：5（或 1，都正确）

关键约束：

• nums[i] != nums[i+1]（相邻元素不相等）
• 边界外视为 -∞，因此如果 nums[0] > nums[1]，则 nums[0] 就是峰值

---

二、解法一：线性扫描

思路分析

遍历数组，找到第一个满足 nums[i] > nums[i-1] && nums[i] > nums[i+1] 的位置。需要特别处理边界：

• i = 0：只需要 nums[0] > nums[1]
• i = n-1：只需要 nums[n-1] > nums[n-2]

完整代码

public class Solution1 {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean leftOk = (i == 0) || (nums[i] > nums[i - 1]);
            boolean rightOk = (i == n - 1) || (nums[i] > nums[i + 1]);
            if (leftOk && rightOk) {
                return i;
            }
        }
        return -1;  // 不会到达这里
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

---

三、解法二：二分查找（比较 mid 和 mid+1）

思路分析

核心思路：通过比较 nums[mid] 和 nums[mid+1] 来判断峰值在哪侧。

• nums[mid] < nums[mid+1]：上升方向，右侧有峰值，令 left = mid + 1。
• nums[mid] > nums[mid+1]（不含相等，题目保证）：下降方向，左侧（含 mid）有峰值，令 right = mid。

为什么这样能保证正确性？

循环不变量：[left, right] 内一定存在峰值。

• 初始时，整个数组必然有峰值（因为数组有限，且边界外是 -∞，所以最大值处就是峰值），不变量成立。
• 每次循环维护不变量（证明见解法三）。
• 循环结束时 left == right，单元素区间里的唯一元素就是峰值。

完整代码

public class Solution2 {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[mid + 1]) {
                // 上升方向，右侧有峰值
                left = mid + 1;
            } else {
                // 下降方向（nums[mid] > nums[mid+1]），左侧含 mid 有峰值
                right = mid;
            }
        }

        return left;  // left == right，峰值位置
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        System.out.println(sol.findPeakElement(new int[]{1, 2, 3, 1})); // 2
        System.out.println(sol.findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4})); // 5
        System.out.println(sol.findPeakElement(new int[]{1})); // 0
        System.out.println(sol.findPeakElement(new int[]{1, 2})); // 1
        System.out.println(sol.findPeakElement(new int[]{2, 1})); // 0
    }
}

复杂度分析

• 时间复杂度：O(log n)。每次循环搜索范围减半。
• 空间复杂度：O(1)。

---

四、解法三最优：深入证明 + 扩展到多峰值收集

思路分析

我们来严格证明解法二的正确性，然后展示如何找出所有峰值。

循环不变量的严格证明：

命题：每次循环前，[left, right] 内一定存在峰值。

初始：整个数组中，最大值必然是峰值（因为左右边界外是 -∞，所以最大值的左右必然小于它）。初始区间包含整个数组，不变量成立。

递推：假设循环前 [left, right] 内存在峰值，证明每个分支后不变量依然成立。

• 分支一：nums[mid] < nums[mid+1]，令 left = mid + 1，新区间 [mid+1, right]。

  • 由 nums[mid] < nums[mid+1]，mid 不是峰值（右邻居更大）。
  • 原区间 [left_old, right] 中的峰值，如果在 [left_old, mid] 范围内，则它必须满足右边 nums[mid] > nums[mid+1]，但这与 nums[mid] < nums[mid+1] 矛盾（除非峰值在 mid 的严格左边，且 mid 在它右侧下坡）。
  • 换个角度想：考虑区间 [mid+1, right]，由于 nums[mid] < nums[mid+1]，沿着 mid+1 起向右走，如果一直在下降，那么 mid+1 就是峰值；如果在某处从降变升，则那个上升点之后必有峰值。总之 [mid+1, right] 必有峰值。

• 分支二：nums[mid] > nums[mid+1]，令 right = mid，新区间 [left, mid]。

  • 同理，mid+1 处不是峰值（左邻居更大）。
  • 区间 [left, mid] 中，从 mid 向左走，若一直下降则 mid 是峰值；若在某处从降变升则有峰值。总之 [left, mid] 必有峰值。

不变量在每步都维持，循环终止时 left == right，该位置就是峰值。

Mermaid 图：峰值二分搜索流程

完整代码（含找所有峰值）

public class Solution3 {
    /**
     * LeetCode 162：找任意一个峰值（O(log n)）
     */
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 扩展：找出所有峰值下标（O(n)，只能线性扫描）
     */
    public List<Integer> findAllPeaks(int[] nums) {
        List<Integer> peaks = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean leftOk = (i == 0) || (nums[i] > nums[i - 1]);
            boolean rightOk = (i == n - 1) || (nums[i] > nums[i + 1]);
            if (leftOk && rightOk) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    /**
     * 变种：山脉数组（先严格递增后严格递减）找峰顶（LeetCode 852）
     * 山脉数组保证有且仅有一个峰值
     */
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;  // 在上升段，峰顶在右边
            } else {
                right = mid;     // 在下降段，峰顶在左边（含 mid）
            }
        }
        return left;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();

        System.out.println(sol.findPeakElement(new int[]{1, 2, 3, 1})); // 2
        System.out.println(sol.findPeakElement(new int[]{1, 2, 1, 3, 5, 6, 4})); // 5

        System.out.println(sol.findAllPeaks(new int[]{1, 2, 1, 3, 5, 6, 4}));
        // 输出：[1, 5]

        System.out.println(sol.peakIndexInMountainArray(new int[]{0, 1, 0})); // 1
        System.out.println(sol.peakIndexInMountainArray(new int[]{0, 2, 1, 0})); // 1
    }
}

复杂度分析

• 时间复杂度：O(log n)。每次循环 right - left 减少至少一半。
• 空间复杂度：O(1)（不计结果列表）。

---

五、举一反三：同类题与模板应用

题号	题目	关键点
852	山脉数组的峰顶索引	山脉数组只有一个峰，代码完全一样
1095	山脉数组中查找目标值	先找峰顶，再在两侧分别二分
1901	寻找峰值 II（二维）	二维矩阵中找峰值，类似逻辑
2529	正整数和负整数的最大计数	利用有序性，二分定位分界点

峰值二分模板：

// 在某个"方向有单调性"的问题中找极值
// 核心：通过比较相邻两个元素，判断"哪个方向走能遇到峰值"
int findPeak(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;   // 上升方向
        } else {
            right = mid;      // 下降方向（含 mid）
        }
    }
    return left;
}

---

六、踩坑实录

坑一：访问 nums[mid+1] 时不检查越界

在二分查找中计算 mid = left + (right - left) / 2，当 left < right 时，mid < right <= nums.length - 1，所以 mid + 1 <= nums.length - 1，访问 nums[mid+1] 是安全的。但如果你的循环条件改成了 left <= right，那就有可能出现 mid == right == nums.length - 1 的情况，此时 mid + 1 越界了。我因为把循环条件写错了，在这里踩过一次坑。

坑二：认为峰值二分只能找"全局最大值"

很多人第一次看到这道题，以为要找全局最大值，然后认为二分找不到全局最大值，就放弃了二分。其实题目要求的是"任意峰值"——局部极大值都可以。这个理解偏差是解题的最大障碍。

坑三：mid 与 mid-1 比较 vs mid 与 mid+1 比较

有人写成 nums[mid] > nums[mid-1] 时向右走，这样也是可以的，但要额外处理 mid == 0 的情况（mid-1 越界）。用 nums[mid] 与 nums[mid+1] 比较，在 left < right 的条件下 mid+1 永不越界，不需要额外处理，更简洁。

坑四：将这道题的二分条件与 LeetCode 153 混淆

LeetCode 153（找旋转数组最小值）用的是 nums[mid] 与 nums[right] 比较；LeetCode 162（找峰值）用的是 nums[mid] 与 nums[mid+1] 比较。两者的逻辑完全不同，不能混用。

我刚开始练题时经常把这两道题的解法搞混，导致两道题都做错了。后来我专门整理了一份"比较对象总结表"，才彻底分清楚。

坑五：单元素数组处理

数组只有一个元素时，left = right = 0，while (left < right) 不进循环，直接返回 0。这是正确的——单个元素的左右都是 -∞，所以它就是峰值。确认你的代码能处理这种边界情况。

---

七、总结

LeetCode 162 是二分查找"抽象应用"的经典例题，它展示了二分查找最本质的能力：只要每步能确定"目标不在某一半"，就可以用二分。这不需要数组全局有序。

核心思路：

• 比较 nums[mid] 和 nums[mid+1]，判断当前处于上升沿还是下降沿。
• 上升沿 → 右侧有峰值 → left = mid + 1。
• 下降沿 → 左侧（含 mid）有峰值 → right = mid。

这个模式和 LeetCode 153 找旋转数组最小值高度相似，但比较的对象不同，要仔细区分。

更重要的是，掌握了这种"方向性二分"的思想，你会发现后面的二分答案（比如 875、1011 等）都是同一个道理的扩展——不是在数组里找值，而是在"答案空间"里用二分收缩。