本文详解为何二分搜索可高效求解“山脉数组峰值索引”问题——虽数组整体无序，但其严格的先升后降结构提供了方向性判断依据，使每次比较都能安全收缩搜索区间。
本文详解为何二分搜索可高效求解“山脉数组峰值索引”问题——虽数组整体无序，但其严格的先升后降结构提供了方向性判断依据，使每次比较都能安全收缩搜索区间。
二分搜索的本质并非依赖“全局有序”，而是依赖决策单调性：即在每一步能根据中点信息，确定目标一定位于左半段或右半段，从而将搜索空间减半。本题中的数组虽非单调排序，但满足严格的“山脉性质”——存在唯一峰值索引 i，使得：
arr[0] （严格递增）-
arr[i] > arr[i+1] > ... > arr[n-1]（严格递减） - 且
arr[i]是全局最大值（即峰值）
正是这一结构性约束，赋予了我们可靠的区间剪枝能力。
关键判断逻辑解析
观察中点 mid 与其右侧邻居 mid + 1 的大小关系：
- 若
arr[mid] > arr[mid + 1]：说明已越过峰值（进入下降段），峰值必然在[l, mid]区间内（因为左侧仍可能存在更高点，而右侧所有元素均小于arr[mid+1]，故更小）。因此令h = mid。 - 若
arr[mid] ：说明尚未到达峰值（仍在上升段），峰值必然在 <code>[mid + 1, h]区间内（因为arr[mid+1]比arr[mid]大，而左侧所有元素均小于arr[mid]，故不可能是峰值）。因此令l = mid + 1。
注意：该逻辑不依赖 arr[mid-1]，仅需一次比较即可定向，简洁高效。
示例追踪（arr = [0,10,5,2]）
| 步骤 | l |
h |
mid |
arr[mid] vs arr[mid+1] |
操作 | 新区间 |
|---|---|---|---|---|---|---|
| 初始 | 0 | 3 | — | — | — | [0,3] |
| 1 | 0 | 3 | 1 |
10 > 5 → True |
h = 1 |
[0,1] |
| 2 | 0 | 1 | 0 | 0 → False |
l = 1 |
[1,1] |
| 结束 | — | — | — | l == h == 1 |
返回 1
|
✅ |
结果正确：峰值 10 位于索引 1。
完整可运行代码（含类型提示与注释）
from typing import List
def peakIndexInMountainArray(arr: List[int]) -> int:
l, h = 0, len(arr) - 1
while l < h:
mid = l + (h - l) // 2
if arr[mid] > arr[mid + 1]:
h = mid # 峰值在左半（含mid）
else:
l = mid + 1 # 峰值在右半（不含mid）
return l注意事项与边界说明
- ✅ 时间复杂度：
O(log n)，标准二分效率； - ✅ 空间复杂度：
O(1)，仅用常量额外空间； - ⚠️ 前提条件：输入必须为合法山脉数组（长度 ≥ 3，严格先升后降，无相等相邻元素），否则行为未定义；
- ⚠️ 索引安全：循环中
mid始终满足mid ，故 <code>arr[mid + 1]恒有效，无需额外越界检查； - ? 推广价值：此思想适用于所有具有“单峰性”或“凸性”的优化问题（如寻找极值点、最小化最大值等），是二分搜索高阶应用的典型范例。
掌握这一思路，便能跳出“二分只用于排序数组”的思维定式，真正理解其作为决策驱动型分治策略的强大本质。
