162. 寻找峰值

https://leetcode-cn.com/problems/find-peak-element/

解法一：二分（递归分治）

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        n = len(nums)
        #边界
        if n == 1:
            return 0
        elif n == 2:  #长度为2时取较大的
            return 0 if nums[0] > nums[1] else 1
        #长度>=3
        else:
            mid = n // 2  #取中点
            #若中点比两侧大，直接去中点
            if nums[mid-1] < nums[mid] > nums[mid+1]:
                return mid
            #若左侧大，说明左侧可能存在山峰，递归处理左侧数组
            elif nums[mid-1] > nums[mid]:
                return self.findPeakElement(nums[:mid])
            #否则递归处理右侧
            else:
                return mid+1 + self.findPeakElement(nums[mid+1:])

解法二：还是二分

其实也不用递归，不仅慢，占用内存还多，直接传统二分

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        low, high = 0, len(nums)-1
        mid = 0
        while low < high:
            mid = (low + high) // 2
            #区间只有两个元素时，特殊处理（防止下面判断越界）
            #直接令mid等于较大元素的下标
            if high - low == 1:
                mid = high if nums[high] > nums[low] else low
                break
            #若mid是山峰
            if nums[mid-1] < nums[mid] > nums[mid+1]:
                break
            #左侧更大，对左侧二分
            elif nums[mid-1] > nums[mid]:
                high = mid-1
            #否则右侧
            else:
                low = mid+1
        #若区间缩减为一个元素，即为所求
        if low == high:
            return low
        #否则mid为所求
        return mid

解法三：暴力

首尾添加负无穷元素，然后一次遍历，结果和二分一样快，奇了怪

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        nums.insert(0, -sys.maxsize)
        nums.append(-sys.maxsize)
        for i in range(len(nums)-1):
            if nums[i-1] < nums[i] > nums[i+1]:
                return i-1  #注意首尾加了辅助元素