含重复元素的山脉数组峰值查找问题：二分查找逻辑异常及优化方案咨询

嗨，我看了你遇到的问题了——你的代码在处理带长平台的山脉数组时，错误地把6当成了峰值，而不是预期的7。这个问题确实出在你当前的二分逻辑上，咱们一步步拆解下问题，再给你优化方案。

问题根源分析 #

你当前的代码有两个关键问题：

1. 相等元素的错误判断：当你计算出中间值m后，如果nums[m]不小于nums[m+1]就直接把r设为m。在你的测试用例里，第一次循环计算m=5（对应值6），此时nums[m]等于nums[m+1]（都是6），代码会执行r=m=5，这就把索引5之后的所有元素（包括峰值7）直接排除在搜索区间外了，后续的二分自然找不到正确的峰值。
2. 提前盲目收缩的潜在风险：你在每次二分迭代前跳过左右重复项的逻辑，虽然在某些场景下能简化问题，但本质上是默认所有平台都在峰值的同一侧，这种假设并不成立，反而可能在复杂场景下进一步缩小正确的搜索区间。

本质上，你默认“只要nums[m]不小于nums[m+1]，峰值就一定在m左侧”，但忽略了核心情况：nums[m]和nums[m+1]相等时，m+1之后可能还存在上升段（比如你的测试用例里，6的平台之后还有7这个峰值）。

优化后的二分查找方案 #

我们需要去掉提前跳过重复项的逻辑，转而在二分的判断逻辑中针对性处理相等元素，通过比较当前中间值和前一个元素的关系，判断平台处于上升段还是下降段，从而正确调整搜索区间。优化后的代码如下：

nums = [1, 3, 6, 6, 6, 6, 6, 7, 4, 3, 2, 1]
l = 0
r = len(nums) - 1
while l < r:
    m = (l + r) // 2
    if nums[m] < nums[m + 1]:
        # 明确处于上升段，峰值一定在右侧
        l = m + 1
    elif nums[m] > nums[m + 1]:
        # 明确处于下降段，峰值一定在左侧或当前位置
        r = m
    else:
        # 处理nums[m] == nums[m+1]的平台情况
        if m > 0 and nums[m] > nums[m - 1]:
            # 平台处于上升段，峰值在右侧
            l = m + 1
        elif m > 0 and nums[m] < nums[m - 1]:
            # 平台处于下降段，峰值在左侧
            r = m
        else:
            # 前后都是相等的平台，逐步缩小左边界，避免错过峰值
            l += 1
print(nums[l])

方案说明 #

• 当nums[m] < nums[m+1]：确定当前在上升段，峰值必然在m+1右侧，直接将左边界移到m+1。
• 当nums[m] > nums[m+1]：确定当前在下降段，峰值必然在m左侧或m本身，将右边界移到m。
• 当nums[m] == nums[m+1]：
  • 如果nums[m] > nums[m-1]：说明当前平台在上升段（比如[1,6,6,7]中的前两个6），峰值在右侧，移动左边界。
  • 如果nums[m] < nums[m-1]：说明当前平台在下降段（比如[7,6,6,1]中的后两个6），峰值在左侧，移动右边界。
  • 如果前后元素都和nums[m]相等：说明当前处于长平台中，逐步缩小左边界，慢慢逼近峰值区间。

这个逻辑既能处理你遇到的“平台后有峰值”的场景，也能正确处理峰值本身是平台、峰值在平台左侧等各种带重复元素的山脉数组情况。

内容来源于stack exchange