如何通过二分查找优化求解山脉数组峰值索引的过程？

本文共计1869个文字，预计阅读时间需要8分钟。

一个数组 +arr+ 被称为山峰数组，需满足以下条件：

• arr.length >= 3
• 存在一个索引 i（0 < i < arr.length - 1），使得：
  • arr[0] < arr[1] < ... < arr[i-1] < arr[i] (严格递增)
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1] (严格递减)

简而言之，山脉数组形如“先上升后下降”的山峰状，其峰值是数组中唯一的最大元素。例如，[0, 2, 1, 0] 是一个山脉数组，其峰值索引为 1，对应的值是 2。

2. 线性扫描方法

最直观的解决方案是遍历整个数组，找到最大值及其对应的索引。由于山脉数组的特性，最大值必然是唯一的峰值。

2.1 算法思路

1. 初始化 peakValue 为 arr[0]，peakIndex 为 0。
2. 从数组的第二个元素开始遍历。
3. 如果当前元素 arr[i] 大于 peakValue，则更新 peakValue = arr[i]，peakIndex = i。
4. 遍历结束后，peakIndex 即为峰值索引。