力扣——寻找峰值
题目
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;
}