​
​

活动地址：CSDN21天学习挑战赛

162. 寻找峰值

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

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

顺序查找

直接从第1个元素找到最后一个元素,nums[i-1]<nums[i]>nums[i+1],即为峰值

class Solution {
    
    public int findPeakElement(int[] nums) {
    
        int n=nums.length;
        if(n<2){
    
            return 0;
        }
        if(nums[0]>nums[1]){
    
            return 0;
        }
        if(nums[n-1]>nums[n-2]){
    
            return n-1;
        }
        for(int i=1;i<n-1;i++){
    
            if(nums[i]>nums[i-1]&&nums[i]>nums[i+1]){
    
                return i;
            }
        }
        return -1;
    }
}

时间复杂度

因为最差情况是找到尾部,因此时间复杂度为O(n²)
这种解题方法不行,必须要用二分查找才能符合题意

二分查找

我们都知道二分查找的条件是数组要有序
这个数组并非有序,那么我们是否不能用二分查找呢
数组有序只是二分查找的一个充分非必要条件
并非有序数组才能二分
只要这个数组存在某种规律,能让数组分成两部分,并且只用在其中的一部分查找

在这一题中,我们发现峰值左右两边的数必定比峰值小
那么我们是否可以用这个规律来定义二分的规则呢
如果中间的数大于右边的数,那么峰值必定在左边,
反之,就在右边

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