为何该代码能在未排序数组中通过二分查找正确定位峰值元素的数组索引？

嘿，你提的这个问题特别好——毕竟大家默认二分查找都是用在完全有序的数组上，突然看到它在这种“半升半降”的数组里工作，确实会困惑。不过先澄清一个关键点：这个输入数组不是随便的未排序数组，它是一个山脉数组（Mountain Array），有着明确的结构：先严格递增，到达一个峰值后严格递减。这个结构特性，就是二分查找能在这里生效的核心原因！

咱们一步一步拆解这个代码的逻辑：

• 首先初始化左指针l在数组开头，右指针h在数组末尾。
• 循环条件是l < h，也就是当两个指针还没重合时继续：
  1. 计算中间位置mid（用l + (h-l)//2是为了避免整数溢出，比(l+h)//2更安全）。
  2. 比较arr[mid]和arr[mid+1]：
     • 如果arr[mid] > arr[mid+1]：说明当前mid处于数组的递减段，峰值肯定在mid或者它的左边（因为递减段的左边才会有递增到顶的峰值），所以把右指针h移到mid，缩小搜索范围到左半部分。
     • 如果arr[mid] < arr[mid+1]：说明当前mid处于数组的递增段，峰值肯定在mid的右边（因为还在往上增，峰值没到），所以把左指针l移到mid+1，缩小搜索范围到右半部分。
• 当循环结束时，l和h会重合，这个位置就是峰值的索引。

咱们用你给的例子arr = [0,10,5,2]走一遍流程，更直观：

1. 初始l=0，h=3，mid=0+(3-0)//2=1。arr[1]=10 > arr[2]=5，所以h=1。
2. 现在l=0 < h=1，mid=0+(1-0)//2=0。arr[0]=0 < arr[1]=10，所以l=0+1=1。
3. 此时l==h=1，循环结束，返回1，正好是峰值元素10的索引，完全正确。

总结一下：二分查找的本质不是依赖数组“整体有序”，而是依赖每次判断都能把搜索范围缩小一半。这个山脉数组的结构刚好满足这个条件——通过比较mid和mid+1，我们总能确定峰值在左半还是右半区间，所以二分查找完全适用，哪怕数组不是整体有序的~

备注：内容来源于stack exchange，提问作者Prasun