BM19 寻找峰值

题目描述

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可
其中，山峰可以位于数组中间，也可以位于数组的左右两边
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

链接：https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tqId=2227748&ru=%2Fpractice%2Fd3df40bd23594118b57554129cadf47b&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj

解题思路

由于只需要找一个峰值，因此可以使用二分法，即不断找满足“mid右边在递增”的mid位置，如果找不到就考虑让high等于mid，从左边开始向右找
比如图中，看到mid=2比7小，就让low=7，此时mid=8；此时mid右边不是递增的，因此只能low=7， high=8，进一步得到不满足low < high，输出low或者high，得到峰值为8

解题代码

class Solution:
    def findPeakElement(self , nums: List[int]) -> int:
        low, high = 0, len(nums)-1
        while low < high:
            mid = int((low+high)/2)
            if nums[mid] < nums[mid+1]:
                low = mid + 1
            else:
                high = mid
        return high