【LeetCode75】第五十五题 寻找峰值

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

给我们一个数组，让我们找出数组里的任意一个峰值，峰值也就是比左右两边的元素更大的值。

直观的做法是直接遍历整个数组，在遍历的过程中判断是否为峰值，那么如果数组长度较大，那么是会很花费时间的。

一个可能有有点颠覆算法小白的做法就是二分查找。有小伙伴可能会疑惑，二分查找不是要求数组有序吗，而且二分查找一般是用来查找特定的值的，而我们这题中都不知道具体的值是多少，这该怎么二分查找？

那二分查找的精髓实际上的每次都排除一半的范围，因为整个数组存在峰值，所以整个数组是局部有序的，我们可以通过二分查找来逐渐锁定范围，直到范围只包括了一个数，那么这个数就是答案。

首先我们先算出范围的中间数，接着和谁比较呢？我们不是找具体的值，所以没法跟具体的值比较。那么我们和中间数右边的一个数做比较，如果中间数比右边的数大，那么是不是峰值就是会存在与中间数的左边（包括中间数）。而如果中间数比右边的数更小，那么峰值就是存在与中间数的右边（不包括中间数）。我们就这样不断缩小范围，知道范围锁定在了一个数身上，那么这个数就是数组的一个峰值。

代码：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l=0;int r=nums.size()-1;    //左闭右闭
        int mid;
        while(l//直到我们将范围锁定到一个数,也就是左右指针重叠
            mid=l+(r-l)/2;
            //如果中间值的右边更大,那么至少一个峰值在中间值的右边,缩小左范围
            if(nums[mid]1]){  
                l=mid+1;
            }else{  //反之缩小右范围,这边r不更新为mid的原因是,r仍然可能是答案
                r=mid;
            }
        }
        return l;
    }
};