162. 寻找峰值

题目链接：https://leetcode-cn.com/problems/find-peak-element/
难度：中等

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

提示：
数组长度：[1, 1000]

题解

思路：
二分法。

• 当nums[mid] < nums[mid+1]：说明峰值在mid右侧
• 当nums[mid] > nums[mid+1]：说明峰值在mid左侧或者就是mid。

二分法的正确性的证明是trivial的。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        length = len(nums)
        if length == 1:
            return 0
        # 避免数组递增导致访问数组外的元素，right应为倒数第二个元素
        left, right = 0, length - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] < nums[mid+1]:
                left = mid + 1
            else:
                right = mid - 1
        return left