题解 | #寻找峰值#

使用二分查找

注意：题目是找峰值元素，不是找最大值

所以找到的波峰不一定是最大值，但它一定是一个峰的峰顶

具体做法：

• step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
• step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
• step 3：如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
• step 4：最后区间收尾相遇的点一定就是波峰。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        // write code here
        int low = 0;
        int high = nums.size()-1;
        while(low < high)//一般退出条件为low == high，除非数组长度不正常
        {
            int mid = (low + high)/2;
            //右边是往下，不一定能找到波峰,所以往左边找
            if(nums[mid] > nums[mid + 1])
               high = mid;//要使条件能到达low == high，则high不能为mid-1，必须为mid
            else //右边是往上，一定能找到波峰，所以往右边找
                low = mid+1;
        }
        return high;
    }
};