算法|寻找峰值-162-[中等]- [二分查找模板

方法一

此方法可以找到第一个满足要求的峰值

package algorithm.binary.search; public class Solution3 { public int findPeakElement(int[] nums) { int idx = 0; for (int i = 1; i < nums.length; ++i) { if (nums[i] > nums[idx]) { idx = i; } } return idx; } }

方法二：二分查找答案中的图很不错：力扣

public int findMin2(int[] nums) { int low = 0; int high = nums.length - 1; while (low < high) { int pivot = low + (high - low) / 2; if (nums[pivot] < nums[high]) { high = pivot; } else { low = pivot + 1; } } return nums[low]; }

思考

首先要注意题目条件，在题目描述中出现了 nums[-1] = nums[n] = -∞，这就代表着只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值

根据上述结论，我们就可以使用二分查找找到峰值

查找时，左指针 l，右指针 r，以其保持左右顺序为循环条件

根据左右指针计算中间位置 m，并比较 m 与 m+1 的值，如果 m 较大，则左侧存在峰值，r = m，如果 m + 1 较大，则右侧存在峰值，l = m + 1

如果x+1比x大，这样一直走下去走到边界，x < x+1,x+1 >-∞ 找到一个峰值
如果x+1比x大，这样一直走下去，走到其中某一步x > x+1,则x就是一个峰值
走的时候往大的方向走，不管左右

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]) { //往大的方向走，所以right 需要左移动位置 //移动后right指向当前的最大值，也就是mid，这个有点不好理解 right = mid; } else { //往大的方向走，所以left 需要右移动位置 //移动后left 指向当前的最大值，也就是 mid + 1，这个有点不好理解 left = mid + 1; } } return left; }

答案
力扣

文章图片
https://leetcode-cn.com/problems/find-peak-element/solution/hua-jie-suan-fa-162-xun-zhao-feng-zhi-by-guanpengc/
答案
【算法|寻找峰值-162-[中等]- [二分查找模板 - II ]】力扣

文章图片
https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode-solution-96sj/