题解 | #寻找峰值#

方法：二分法

首先根据题目的条件2和条件3，可以得出一个结论：数组一定能找到峰值。因为数组相邻的元素不会相等，所以相邻的元素一定是有递增或者递减的趋势。如果数组是一个递增数组和递减数组，根据条件2也可以得到：递增数组的峰值是最后一个元素；递减数组的峰值是第一个元素。

步骤：

1、找到数组的中间元素mid；

2、判断mid与mid+1的大小关系。

如果mid+1大于mid时，右侧一定能找到峰值。因为右边是向上的会对应两种情况：1、右侧会在某个元素开始下降；2、右侧一直向上递增。第一种情况：如果右侧会在某个数组元素开始下降，那么这个数组元素就是峰值；第二种情况，如果右侧一直向上递增，这时候可能有人就会觉得那不就是没有峰值了，但是按照题目中的条件： nums[-1] = nums[n] = −∞，这时峰值就是数组的最后一个元素。

如果mid+1小于mid时，右侧不一定能找到峰值，则从左侧去寻找峰值。

3、不断地迭代缩小范围，最后一定能找到峰值。

时间复杂度：o(logⁿ)

空间复杂度：o(1)

class Solution {
  public:
    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])
                right = mid;
            //右边是往上，一定能找到波峰
            else
                left = mid + 1;
        }
        //其中一个波峰
        return right;
    }
};