每日一题 162. 寻找峰值（中等，二分搜索）

2023-12-18 19:13:15

在这里插入图片描述

二分搜索

  1. 关键在于，如果 mid 不是峰值索引，假设 mid + 1 大于 mid，显然 mid + 1 有可能是峰值索引，同理可知如果 mid + 1 不是，那么 mid + 2 就有可能是，以此类推，由于 num[n] 是负无穷，因此从 mid + 1 到数组末尾之间必定存在峰值索引
  2. 由 1 我们可以得到推论，当一个值不是峰值时，导致它不是峰值的那一边就必定存在峰值，因此二分得解
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = (l + r) >> 1
            if (m == len(nums) - 1 or nums[m] > nums[m + 1]) and (m == 0 or nums[m] > nums[m - 1]):
                return m
            if m != len(nums) - 1 and nums[m] <= nums[m + 1]:
                l = m
                continue
            r = m
        
        return l

文章来源:https://blog.csdn.net/qq_46636391/article/details/135066992
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。