题目描述

峰值定义为比左右相邻元素大的元素。

给定一个数组 nums，保证 nums[i] ≠ nums[i+1]，请找出该数组的峰值，并返回峰值的下标。

数组中可能包含多个峰值，只需返回任意一个即可。

假定 nums[-1] = nums[n] = -∞。

样例

样例1
输入：nums = [1,2,3,1]
输出：2
解释：3是一个峰值，3的下标是2。
样例2
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：数组中有两个峰值：1或者5，返回任意一个即可。
此题与三分思想有些类似，比如a[mid],a[mid-1]大小，a[mid]>a[mid+1]则波峰位置i一定（0<=i<=mid,此时r（r=mid）左移舍弃右半段）;
同理，a[mid]<a[mid+1],l=mid+1,舍弃左半段，直到扫描到最终位置，因为 nums[-1] = nums[n] =-∞，如果最终位置在0，num.size()-1也是波峰；
因此，只需要对整段二分即可，时间复杂度logn

class Solution {//方法一
public:
    int findPeakElement(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]>=nums[mid+1]) r=mid;//因为mid取不到size-1的位置上，故mid+1不会越界
            else l=mid+1;
        }
        return l;
    }
};
class Solution {//方法二
public:
    int findMin(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(nums[mid]>=nums[mid-1]) l=mid;//同理不会取到mid=0,也不会越界
            else r=mid-1;
        }
        return nums[l];
        return 0;
    }
};