题目解析
162. 寻找峰值
题目中有一个很重要的提示:对所有有效的i都存在nums[i] != nums[i+1],因此这道题不需要考虑nums[mid] 和 nums[mid+1]之间的相等与否的关系
算法讲解
1. 暴力枚举
我们按照顺序判断每个数字是否是当前的峰值,如果是直接返回,如果不是继续寻找。如果寻找的数组末尾还没有寻找到,那么就是数组的最后一个元素
2. 二分法
如果当前的nums[i] < nums[i+1] 说明i左侧不一定会出现峰值,因为它是上升趋势,峰值一定会出现在i+1的右侧区域
反之,如果当前的nums[i] > nums[i+1] 说明i左侧一定会出现峰值,但是i+1右侧不一定会出现,因为它是下降趋势的
又因为题目中说明没有一个合理的i,存在num[i] == nums[i+1],因此我们不需要对此情况进行判断
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while(left < right)
{
int mid = left + (right - left) / 2;
//左边一定存在峰值
if(nums[mid] > nums[mid + 1])right = mid;
//右边一定存在峰值
if(nums[mid] < nums[mid + 1])left = mid + 1;
}
return left;
}
};