find-peak-element

题目描述

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

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

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

题解

线性扫描

int findPeakElement(vector<int>& nums) {
    int index=0;
    while(index+1<nums.size()&&nums[index]<nums[index+1])index++;
    return index;
}

二分法

nums可视为交替的升序和降序序列。与右边相邻元素比较，可以知道当前是在上升坡度还是下降坡度。找到中间元素mid，若mid位于下降坡度，则峰值在左边；若mid位于上升坡度，则峰值在右边。

int findPeakElement(vector<int>& nums) {
    int left=0;int right=nums.size()-1;
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[mid]<nums[mid+1])
            left=mid+1;
        else
            right=mid;
    }
    return left;
}