如何将山脉数组峰值索引查找从线性扫描优化至高效二分查找法？

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

在算法领域，山峰数组是一种特殊的数组结构，其定义如下：

1. arr.length >= 3。
2. 存在某个索引 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 到结尾严格递减)。

我们的目标是给定一个山脉数组 arr，返回其峰值索引 i。此外，通常要求算法的时间复杂度为 O(log(arr.length))。

方法一：线性扫描法

线性扫描法是一种直观且易于理解的解决方案。由于山脉数组只有一个峰值，且这个峰值是数组中的最大元素，我们可以通过遍历整个数组来找到这个最大值及其对应的索引。

原理

算法从数组的第一个元素开始，依次向后遍历。在遍历过程中，它会维护一个当前找到的最大值 (peakValue) 和该最大值对应的索引 (peakIndex)。每当遇到一个比 peakValue 更大的元素时，就更新 peakValue 和 peakIndex。遍历结束后，peakIndex 即为山脉数组的峰值索引。

示例代码

public class Solution { public static int peakIndexInMountainArray(int[] arr) { // 初始化峰值和峰值索引。