山脉数组中如何用二分查找目标值？

简化版

山脉数组先严格递增，再严格递减。

查找目标值通常分三步：先用二分找到峰顶下标；再在左侧递增区间做普通二分；如果没找到，再在右侧递减区间做反向二分。

关键是右半边是降序，比较方向要反过来。

详细版

山脉数组形如：

1, 3, 5, 7, 6, 4, 2

峰顶是 7。

找峰顶：

if arr[mid] < arr[mid + 1]:
  left = mid + 1
else:
  right = mid

找到峰顶后：

区间	顺序	二分方式
[0, peak]	升序	普通二分
[peak+1, n-1]	降序	比较方向反过来

如果题目要求返回最小下标，应该先搜左侧。

完整版教学

1. 什么是山脉数组

山脉数组满足：

arr[0] < arr[1] < ... < arr[peak]
arr[peak] > arr[peak+1] > ... > arr[n-1]

也就是先上升再下降。

它不是整体有序，但由两个有序区间组成。

2. 为什么先找峰顶

峰顶把数组分成两段：

• 左边严格递增；
• 右边严格递减。

只要找到峰顶，就能把一个无序整体转成两个有序区间的查找问题。

山脉数组查找的核心拆解是：先找峰，再分别二分两侧。

3. 峰顶怎么二分

比较 arr[mid] 和 arr[mid + 1]。

如果：

arr[mid] < arr[mid + 1]

说明当前位置在上坡，峰顶在右边。

否则说明当前位置在下坡或峰顶附近，峰顶在 mid 或左边。

while left < right:
  mid = left + (right - left) / 2
  if arr[mid] < arr[mid + 1]:
    left = mid + 1
  else:
    right = mid

4. 左侧升序二分怎么做

左侧 [0, peak] 是升序。

普通二分：

if arr[mid] < target:
  left = mid + 1
else:
  right = mid - 1

如果找到，直接返回。

如果题目要求最小下标，左侧优先是合理的，因为左侧下标都比右侧小。

5. 右侧降序二分怎么做

右侧是降序。

比较方向要反过来：

if arr[mid] < target:
  right = mid - 1
else:
  left = mid + 1

因为在降序数组里，当前值比 target 小，目标应该在左边更大的区域。

6. API 调用次数怎么考虑

有些题把山脉数组包装成 API：

MountainArray.get(index)
MountainArray.length()

并限制调用次数。

这时要避免重复调用同一个下标，可以缓存 get(index) 的结果。

优化	作用
缓存 get	减少 API 调用
先搜左侧	满足最小下标
峰顶只找一次	避免重复计算

7. 复杂度怎么分析

找峰顶是：

O(log n)

两侧二分各是：

O(log n)

总复杂度仍然是 O(log n)，空间 O(1)，如果加缓存则空间和缓存数量相关。

8. 常见误区与追问

• 误区：山脉数组不能二分。 它整体不有序，但可以先找峰顶再对两边分别二分。
• 误区：右侧也用升序二分模板。 右侧是降序，比较方向必须反过来。
• 误区：找到右侧目标就一定返回。 如果要求最小下标，应先查左侧。
• 追问：如何找峰顶？ 比较 arr[mid] 和 arr[mid+1] 判断上坡还是下坡。
• 追问：API 版本如何优化？ 对 get(index) 做缓存，减少重复访问。