【LeetCode】每日一题 2023_12_18 寻找峰值 （二分）

刷题前唠嗑

LeetCode？启动！！！

题目：寻找峰值

题目链接：162. 寻找峰值

题目描述

代码与解题思路

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left+(right-left)/2
        if nums[mid] < nums[mid+1] {
            left = mid+1
        } else if nums[mid] > nums[mid+1] {
            right = mid
        }
    }
    return right
}

乍一看，我们好像无从下手，那就慢慢分析，看看该怎么解决。

题目要求我们要查找数组中任意一个峰值，那我们可以怎么找到峰值呢？我们可以分析到，其实这个数组无非就分为连个区间，一个是递增区间，一个是递减区间，而峰值就是两个区间交替的标志

假设我们随机找一个点，如果他比右边位置的值小，那就证明他在一个递增的区间；如果他比右边的位置的值大，那就证明他在一个递减的区间

通过这个性质，我们使用二分算法，当 nums[mid] < nums[mid+1] 时，在一个递增的区间，山顶必定在 mid+1 以及之后的位置；当 nums[mid] > nums[mid+1] 时，在一个递减的区间，山顶则可能在 mid 或者是之前的位置（这里要注意了，山顶有可能就是 mid 位置）

所以 right = mid，而不需要 -1 的操作。也因为这里不需要 -1，当 left == right 的时候，如果我们已经找到山顶了，那该怎么跳出循环？

这里我们可以选择特判一下，也可以使用 left < right 作为循环条件
————————————————
版权声明：本文为CSDN博主「戊子仲秋」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Locky136/article/details/133382439

结语

之前写过这篇文章的题解，这下可以自己引用自己了，真好玩，嘿嘿