二分查找题目：寻找峰值

题目

标题和出处

标题：寻找峰值

出处：162. 寻找峰值

难度

6 级

题目描述

要求

峰值元素是指其值严格大于左右相邻值的元素。

给定一个长度为 $\text{n}$ 的整数数组 $\text{nums}$，找到一个峰值元素并返回其下标。如果数组包含多个峰值，则返回任何一个峰值的下标。

可以假设 $\text{nums[-1]}=\text{nums[n]}=-\infty$。

要求时间复杂度是 $\text{O(log n)}$。

示例

示例 1：

输入：$\text{nums = [1,2,3,1]}$
输出：$\text{2}$
解释：$\text{3}$ 是峰值元素，返回其下标 $\text{2}$。

示例 2：

输入：$\text{nums = [1,2,1,3,5,6,4]}$
输出：$\text{1}$ 或 $\text{5}$
解释：可以返回峰值 $\text{2}$ 的下标 $\text{1}$，或者峰值 $\text{6}$ 的下标 $\text{5}$。

数据范围

• $\text{1}\le \text{nums.length}\le \text{1000}$
• ${\text{-2}}^{\text{31}}\le \text{nums[i]}\le {\text{2}}^{\text{31}}-\text{1}$
• 对于所有有效的 $\text{i}$ 都有 $\text{nums[i]}\ne \text{nums[i + 1]}$

解法

思路和算法

由于题目要求在长度为 $n$ 的数组中寻找峰值的时间复杂度是 $O(\log n)$，因此需要使用二分查找的做法寻找峰值。二分查找的过程中需要判断可能存在峰值的下标范围，缩小查找的下标范围。

考虑数组 $\text{nums}$ 中的两个相邻下标 $i$ 和 $j$ 处的元素，其中 $0\le i,j<n$ 且 $j-i=1$。由于 $\text{nums}[i]\ne \text{nums}[j]$，因此 $\text{nums}[i]$ 和 $\text{nums}[j]$ 的大小关系是 $\text{nums}[i]>\text{nums}[j]$ 或 $\text{nums}[i]<\text{nums}[j]$。

当 $\text{nums}[i]>\text{nums}[j]$ 时，下标范围 $[0,i]$ 中一定存在峰值；当 $\text{nums}[i]<\text{nums}[j]$ 时，下标范围 $[j,n-1]$ 中一定存在峰值。因此可以根据 $\text{nums}[i]$ 和 $\text{nums}[j]$ 的大小关系判断可能存在峰值的下标范围，并在更小的范围内查找峰值。

基于上述思路，可以使用二分查找的做法寻找峰值。

用 $\text{low}$ 和 $\text{high}$ 分别表示二分查找的下标范围的下界和上界，初始时 $\text{low}$ 和 $\text{high}$ 分别为数组的最小下标和最大下标。每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向下取整，比较 $\text{nums}[\text{mid}]$ 和 $\text{nums}[\text{mid}+1]$ 的大小关系（注意当 $\text{low}<\text{high}$ 时，$\text{mid}\le n-2$，因此下标 $\text{mid}+1$ 不会超出数组下标范围），判断可能存在峰值的下标范围，调整查找的下标范围。

• 如果 $\text{nums}[\text{mid}]>\text{nums}[\text{mid}+1]$，则下标范围 $[\text{low},\text{mid}]$ 中可能存在峰值，在该下标范围中继续查找。

• 如果 $\text{nums}[\text{mid}]<\text{nums}[\text{mid}+1]$，则下标范围 $[\text{mid}+1,\text{high}]$ 中可能存在峰值，在该下标范围中继续查找。

当 $\text{low}=\text{high}$ 时，查找结束，此时 $\text{nums}[\text{low}]$ 即为峰值，返回 $\text{low}$。

证明

为了证明上述二分查找做法的正确性，对于 $0\le i,j<n$ 且 $j-i=1$，需要证明：当 $\text{nums}[i]>\text{nums}[j]$ 时，下标范围 $[0,i]$ 中一定存在峰值；当 $\text{nums}[i]<\text{nums}[j]$ 时，下标范围 $[j,n-1]$ 中一定存在峰值。可以使用反证法证明。

当 $\text{nums}[i]>\text{nums}[j]$ 时，假设下标范围 $[0,i]$ 中不存在峰值。由于 $\text{nums}[i]$ 不是峰值，因此 $\text{nums}[i]<\text{nums}[i-1]$。从下标 $i-1$ 向左遍历数组 $\text{nums}$，对于每个下标 $k$，由于 $\text{nums}[k+1]$ 和 $\text{nums}[k]$ 都不是峰值，因此 $\text{nums}[k+1]<\text{nums}[k]<\text{nums}[k-1]$，即数组 $\text{nums}$ 在下标范围 $[0,i]$ 中单调递减。由于 $\text{nums}[-1]=-\infty$，因此必有 $\text{nums}[0]>\text{nums}[-1]$，此时 $\text{nums}[0]$ 是峰值。由此可以得到以下结论。

• 如果下标范围 $[1,i]$ 中存在峰值，则下标范围 $[0,i]$ 中存在峰值。

• 如果下标范围 $[1,i]$ 中不存在峰值，则 $\text{nums}[0]$ 是峰值，下标范围 $[0,i]$ 中存在峰值。

因此，下标范围 $[0,i]$ 中一定存在峰值。

当 $\text{nums}[i]<\text{nums}[j]$ 时，利用 $\text{nums}[n]=-\infty$，同理可知下标范围 $[j,n-1]$ 中一定存在峰值。

代码

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

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。二分查找的次数是 $O(\log n)$，每次查找的时间是 $O(1)$，时间复杂度是 $O(\log n)$。

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