题解 | #寻找峰值#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    //二分查找
    //可能会有同学很困惑本题为什么能用二分查找呢？二分查找不是只能用于有序的数组吗?
    //其实二分查找的本质是每次二分之后想查找的元素一定可以确定在某一边，只要符合这种情况都可以使用二分查找
    int findPeakElement(vector<int>& nums) {
        // write code here
        //首先检查数组最左边和最右边的值是否有可能是极大值
        if(nums[0]>nums[1])
            return 0;
        if(nums[nums.size()-1]>nums[nums.size()-2])
            return nums.size()-1;
        int size=nums.size();
        int left=0,right=size;//定义二分查找的区间，为左闭右开
        while(left<right){//因为区间是左闭右开的所以循环终止条件是<而不是<=
            int mid=(right-left)/2+left;//防止溢出
            if(nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1])
                return mid;
            else if(nums[mid]<nums[mid-1]){//画图由趋势可知，此时在left到mid上肯定会有极大值
                right=mid;//因为是左闭右开区间，所以让right等于mid
            }
            else if(nums[mid]<nums[mid+1]){
                left=mid+1;//因为是左闭右开区间所以left等于mid+1
            }
        }
        return left;//没找到
    }
};