如何将山脉数组峰值索引查找从线性扫描优化至O(logN)的二分查找？

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

在深入探讨峰值查找方法之前，首先需要明确山峰数组的定义。一个数组被称为山峰数组，如果它满足以下条件：

• arr.length >= 3：数组的长度至少为3。
• 存在一个索引 i，满足 0 < i < arr.length - 1，使得：
  • arr[0] < arr[1] < ... < arr[i-1] < arr[i]：数组从开头到索引 i 是严格递增的。
  • arr[i] > arr[i+1] > ... > arr[arr.length-1]：数组从索引 i 到结尾是严格递减的。

简而言之，山脉数组就像一座山，先上升到最高点（峰值），然后下降。我们的目标就是找到这个最高点（峰值）的索引 i。

直观的线性扫描方法

最直接的思路是遍历整个数组，找到其中最大的元素，并记录其索引。由于山脉数组的特性，最大的元素必然是峰值。

实现原理

1. 初始化一个变量 peakValue 来存储当前找到的最大值，以及 peakIndex 来存储其对应的索引。
2. 遍历数组中的每一个元素。
3. 如果当前元素的值大于 peakValue，则更新 peakValue 为当前元素的值，并更新 peakIndex 为当前元素的索引。
4. 遍历结束后，peakIndex 即为山脉数组的峰值索引。