题目地址

162. 寻找峰值

解题思路

二分搜索的关键就是根据每一次得到的mid来确定目标值的区间范围，根据本题的寻找峰值，那么就有三种情况：

  1. 下标mid对应的元素，大于它左边和右边的元素，则mid就是峰值下标，直接返回
  2. 下标mid对应的元素，小于它左边的元素，此时区间左移
  3. 下标mid对应的元素，大于它左边的元素，此时区间右移

注意，本题有$nums[-1] = nums[n] = -∞nums[−1]=nums[n]=−∞$，所以不管往左还是往右，必定会存在一个峰值元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0 
        right = len(nums) - 1
        min_val = -float("inf")
        while left <= right:
            mid = left + (right - left) // 2
            val = nums[mid]
            val_b = min_val if mid == 0 else nums[mid-1]
            val_a = min_val if mid == len(nums)-1 else nums[mid+1]
            if val_b < val and val > val_a:
                return mid
            if val_b > val:
                right = mid - 1
            else:
                left = mid + 1
        return left