为何二分查找可用于无序列表？峰值元素查找代码原理疑问

我完全懂你的困惑！之前我也以为二分查找只能用在严格有序的数组里，第一次看到用它找峰值的时候也懵了好一阵子，咱们一步步拆解这个逻辑。

首先先明确题目里的核心定义和要求：

峰值元素指大于其相邻元素的元素，给定满足num[i]≠num[i+1]的输入数组，需找到任意一个峰值元素并返回其索引；数组若含多个峰值，返回任意一个即可。

举个直观的例子：

• 输入数组：[1, 4, 5, 7, 4, 3, 1]，峰值索引为3（对应元素7）

你提供的实现代码如下：

public static int getPeakElement(int[] array, int left, int right) {
    if (left == right) {
        return left;
    }
    int mid = (left + right) / 2;
    if (array[mid] > array[mid + 1]) {
        return getPeakElement(array, left, mid);
    }
    return getPeakElement(array, mid + 1, right);
}

核心原理拆解 #

这个二分查找的核心不是依赖数组整体有序，而是依赖每一步都能锁定存在峰值的子区间，咱们分点说：

• 前提：数组的隐性特性
  题目里有两个关键条件：一是num[i]≠num[i+1]，没有相邻相等的元素；二是可以把数组的两端（第一个元素的左边、最后一个元素的右边）看作是负无穷。这意味着：

  • 如果第一个元素比第二个大，它就是峰值；
  • 如果最后一个元素比前一个大，它就是峰值；
  • 数组里不可能出现平坡，每一步的比较都能得到明确的大小关系。

• 二分的逻辑：每一步都能缩小峰值范围
  看代码里的关键判断：

  1. 当array[mid] > array[mid + 1]时，我们选择在[left, mid]区间继续查找：
     这是因为从left到mid的区间里一定存在峰值。假设mid左边的元素一直递增到mid，那mid本身就是峰值；如果左边有下降的节点，那下降前的那个元素就是峰值；就算一路往左到left，left如果比右边元素大，left就是峰值，否则中间必然有一个上升后下降的转折点——也就是峰值。
  2. 当array[mid] < array[mid + 1]时，我们选择在[mid+1, right]区间继续查找：
     同理，mid+1到right的区间里一定存在峰值。如果mid+1右边的元素一直递增到right，那right就是峰值；如果中间有下降，下降前的元素就是峰值；就算一路到right，right本身也符合峰值的判定（因为它比左边的mid+1大，右边是负无穷）。

• 终止条件：区间只剩一个元素
  当left == right时，这个区间是经过无数次筛选后锁定的“必含峰值”的区间，此时这个唯一的元素必然是峰值，直接返回它的索引即可。

说白了，这个二分查找的思路是利用局部的大小关系，不断排除不可能存在峰值的区间，最终定位到一个峰值，完全不需要数组整体有序~

内容的提问来源于stack exchange，提问作者Rachel