leetcode(162):寻找峰值 Find Peak Element

题目

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[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。

思路

根据题目提示，存在一个O(log n)的算法。下意识想到可能是二分查找了。用二分查找，找到满足nums[i-1] < nums[i] < nums[i+1]的i即可。

由于假定了nums[-1] = nums[n] = -∞，可以认为区间[0,n)中存在一个点是极大值点，用二分法找出这个极大值点即可。假定任何情况下，lo左边的函数值小于lo点的函数值，hi点的函数值小于hi左边的函数值，令mid=(lo+hi)/2，现在要考虑迭代的条件。

1，当lo<hi时，要比较mid,mid-1,mid+1三点的函数值。mid一定是在当前区间里的，而mid+1不一定，因为mid+1可能等于hi。当mid+1=hi时，得出结论mid函数值>mid+1函数值，这个结论没有什么用，因为它既不能把lo提升到mid，也不能把hi缩小到mid。所以转而考虑mid-1的情形。

2，mid-1也不一定在当前区间中，因为可能出现mid=low，mid-1=low-1。出现这种情况时，必然有hi=lo+1。那么区间[lo,hi)中只有一个点lo，它就是要找的答案。

3，如果mid-1在当前区间中，也就存在函数值，可以用于比较。若mid-1函数值<mid函数值，则左边的区间和整个大区间性质相似，必然存在一个极值点，可以把[lo,hi)缩小到[mid,hi)；否则的话，就是mid-1函数值>mid函数值，右边区间和整个区间的性质相似，必然存在一个极值点，可以把[lo,hi)缩小到[lo,mid)。

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if(len(nums)==0):
            return  -1
        if(len(nums) == 1):
            return 0
        lenght = len(nums)
        if(nums[0]>nums[1]):
            return  0
        elif(nums[lenght-1]>nums[lenght-2]) :
                return  lenght-1
        

        begin  = 0
        end =lenght
        while(begin<=end):
            middle = begin + (end-begin)//2
            if(nums[middle-1]<nums[middle]  and  nums[middle]>nums[middle+1] ):
                return  middle
            elif(nums[middle-1]>nums[middle] ):
                end = middle -1
            else:
                begin = middle+1