本文详解为何二分查找可在未全局排序的“山形数组”（先严格递增后严格递减）中正确找到唯一峰值索引，核心在于利用局部单调性推导搜索区间，而非依赖全局有序。
本文详解为何二分查找可在未全局排序的“山形数组”（先严格递增后严格递减）中正确找到唯一峰值索引，核心在于利用局部单调性推导搜索区间，而非依赖全局有序。
二分查找的本质并非“仅适用于已排序数组”，而是适用于具有明确区间淘汰性质（monotonic decision property）的问题：即每次比较后，能根据某种确定性规则排除一半候选空间。本题中的 peakIndexInMountainArray 正是这一思想的典范应用。
给定山形数组 arr（满足：存在唯一索引 i，使得 arr[0] arr[i+1] > ... > arr[n-1]，且无相等相邻元素），峰值即为全局最大值，且位于“上坡转下坡”的拐点。关键洞察如下：
- 若
arr[mid] > arr[mid + 1]：说明mid处已处于“下坡段”，峰值必然在[l, mid]区间内（因为从mid向右持续下降，不可能再出现更大值）； - 若
arr[mid] ：说明 <code>mid处仍处于“上坡段”，峰值必然在[mid + 1, h]区间内（因为从mid向左所有元素均小于arr[mid]，更小于arr[mid+1]及其右侧更大值）。
该逻辑保证了每次迭代都能安全收缩搜索范围，且不遗漏峰值。注意：算法始终比较 mid 与 mid+1，因此循环条件设为 l （避免越界），且更新时 <code>h = mid（而非 mid-1）和 l = mid + 1（而非 mid），确保收敛至唯一峰值索引。
以下是精简可靠的实现：
from typing import List
def peakIndexInMountainArray(arr: List[int]) -> int:
l, h = 0, len(arr) - 1
while l arr[mid + 1]:
h = mid # 峰值在左半（含mid）
else:
l = mid + 1 # 峰值在右半（不含mid）
return l
✅ 正确性保障：
- 输入必须严格满足山形约束（无平台、有唯一峰），否则行为未定义；
- 时间复杂度稳定为 O(log n)，远优于线性扫描的 O(n)；
- 空间复杂度为 O(1)，无需额外存储。
⚠️ 注意事项：
- 该解法不适用于一般无序数组——它高度依赖山形结构隐含的单峰性和单调分段特性；
- 若数组可能含重复元素（如
[1,2,2,1]），需额外处理边界逻辑，原代码可能失效； - 实际使用前建议校验输入是否真正构成山形，尤其在生产环境中。
总结而言，这是对二分思想的一次优雅拓展：当问题具备“方向性可判定性”（即能通过一次比较判断目标所在半区）时，即使整体无序，二分仍是最优策略。
