162. 寻找峰值(中)

• 题目
• 题解：二分

题目

• 峰值元素是指其值严格大于左右相邻值的元素。
  给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
  你可以假设 nums[-1] = nums[n] = -∞ 。
  你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

题解：二分

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if nums is None:
            return -1
        if len(nums)==1:#数组中唯一的元素可以被认为是峰值
            return 0
        left=0
        right=len(nums)-1
        while left<=right:#直到left>right跳出循环
            mid=left+(right-left)//2
            if mid<len(nums)-1 and nums[mid]>nums[mid-1] and nums[mid]>nums[mid+1]:#确保mid+1 是一个有效的索引，如果mid的值比左右两边都大，满足峰值直接返回
                return mid
            elif mid==len(nums)-1 or nums[mid]>nums[mid+1]:#当mid为最后一个元素时，mid+1会溢出，所以加上mid==len(nums)-1判断
            #当mid的值大于mid+1，说明右边元素不大于mid,峰值在左边,更新右指针的值，把范围缩在左边
                right=mid-1
            else:
                left=mid+1
        return left #如果没有找到峰值，当数组递增时，left指向最后一个元素；当数组递减时，left指向第一个元素

• 会遇到越界的情况，注意加上限制判断

为什么是比较mid和mid+1在数组中的值，而不像标准的二分模板比较的是mid和left/right来缩小寻找范围？
一开始我们可以这样写，当遇到1213564这个测试案例的时候就明白了，中间元素与左右比较并不能得到某一边有序，而缩小范围。
所以还是按照题目意思峰值元素是比左右两边都大的元素，依次做判断条件