题目

162. 寻找峰值 - 力扣（LeetCode）

思路

第一想法就是直接遍历，时间复杂度为O(n)，肯定超时了。

然后就想到用二分，但是数组又不一定是有序的。仔细一思考，好像也可以用，关键在于这个峰值的性质。
按照题目当中的条件，数组当中总有一个峰值，传统二分查找依赖数组的全局有序性，而这里利用的是峰值的局部性。

• 如果 nums[mid] < nums[mid + 1]：

  • 峰值一定在右侧：
    • 如果右侧某段存在上升趋势，最终会遇到一个峰值或数组的末尾（nums[n] = -∞）。
    • 右侧包含可能的峰值，因此缩小范围到 [mid + 1, high]。

• 如果 nums[mid] > nums[mid + 1]：

  • 峰值可能是 mid 或在左侧：
    • 左侧包含可能的峰值，因此缩小范围到 [low, mid]。

代码

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