二分法-寻找峰值

在这里插入图片描述

求解代码

因为本题假设nums[-1]=nums[n]=-∞，所以，只要数组中存在一个元素比相邻的元素大，那么沿着它就一定可以找到一个峰值。

使用二分查找，比较mid和mid+1位置的值，如果mid位置的值更大，则左侧存在峰值；

如果mid+1位置的值更大，则右侧存在峰值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public int findPeakElement (int[] nums) {
        int left = 0;
		int right = nums.length;

		while(left<right){
			int mid = left+((right-left)>>1);
			if(nums[mid]>nums[mid+1]){
				right=mid;
			}else{
				left=mid+1;
			}
		}
		return left;
    }

注意⚠️：

这里说明一下为什么无序数组也能使用二分查找，主要是这道题通过比较nums[mid]和nums[mid+1]，可以确定峰值的位置区间，这满足二分的核心条件，所以无序也能用二分。