山脉数组峰值索引查找：优化与二分查找详解_技术教程

本文深入探讨了如何在山脉数组中高效查找峰值索引的问题。我们将分析一种常见的线性扫描方法及其局限性，并重点介绍符合O(logN)时间复杂度要求的二分查找算法。通过详细的逻辑解析和代码示例，帮助读者理解并正确实现山脉数组的峰值查找，避免常见的陷阱。

1. 引言：理解山脉数组与峰值问题

在计算机科学中，"山脉数组"（mountain array）是一种特殊的数组结构，它具有以下明确的特性：

数组的长度至少为3。
存在一个索引 i（0 arr[i+1] > ... > arr[arr.length-1]。

我们的目标是找到这个唯一的峰值索引 i。特别地，问题要求解决方案的时间复杂度必须达到 O(log(arr.length))，这强烈暗示我们需要采用二分查找（Binary Search）策略。

2. 初始二分查找尝试及问题诊断

许多开发者在面对 O(logN) 复杂度要求时，会自然想到二分查找。然而，二分查找的实现细节，尤其是在非简单查找场景下，常常容易出错。以下是一个常见的、存在问题的二分查找尝试：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            // 尝试判断 mid 是否为峰值，但条件过于复杂且不准确
            if (mid == 0 || (arr[mid] >= arr[mid - 1]) && (mid == high || arr[mid] >= arr[mid + 1]))
                return mid;
            // 错误的搜索区间更新逻辑
            else if (mid > 0 || arr[mid - 1] > arr[mid]) {
                low = mid + 1;
            }
            high = mid - 1; // 此行无条件执行，导致逻辑混乱
        }
        return mid;
    }
}

问题诊断：

峰值判断条件复杂且不准确： mid==0 或 mid==high 不可能是峰值，因为山脉数组定义要求峰值 i 满足 0 = arr[mid-1] 和 arr[mid] >= arr[mid+1] 的组合判断，在边界处理和逻辑上容易出错，未能充分利用山脉数组的单调性。
搜索区间更新策略混乱： else if (mid > 0 || arr[mid-1] > arr[mid]) 的条件并不明确指向峰值在左侧还是右侧。更严重的是，high = mid - 1; 语句在 else if 块外部无条件执行，这意味着无论 mid 是在上升坡还是下降坡，high 都会被错误地向左移动，导致搜索范围收缩不正确，甚至错过峰值。
循环条件与返回值的配合： while(low

3. 线性扫描方法：简单但非最优

在某些情况下，一个简单直观的线性扫描（Linear Scan）方法也能找到峰值。这种方法遍历整个数组，记录当前遇到的最大值及其索引。由于山脉数组的特性，数组中的最大值必然是峰值。

public class Solution {
    public static int peakIndexInMountainArray(int[] arr) {
        int peakValue = 0; // 初始值应根据实际数据范围调整，或使用arr[0]
        int peakIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            int value = arr[i];
            if (value > peakValue) {
                peakValue = value;
                peakIndex = i;
            }
        }
        return peakIndex;
    }

    public static void main(String[] args) {
        System.out.println("Set 1: " + peakIndexInMountainArray(new int[]{0,1,2})); // 2
        System.out.println("Set 2: " + peakIndexInMountainArray(new int[]{0,1,0})); // 1
        System.out.println("Set 3: " + peakIndexInMountainArray(new int[]{0,2,1,0})); // 1
        System.out.println("Set 4: " + peakIndexInMountainArray(new int[]{0,10,5,2})); // 1
        System.out.println("Set 5: " + peakIndexInMountainArray(new int[]{0,100,500,2})); // 2
    }
}

分析：

工作原理： 此方法通过简单遍历数组，比较每个元素与当前记录的 peakValue，若当前元素更大，则更新 peakValue 和 peakIndex。对于山脉数组而言，其最大值就是峰值，因此此方法能正确找到峰值索引。
局限性： 尽管它能得到正确结果，但其时间复杂度为 O(N)，其中 N 是数组的长度。这不符合题目中明确要求的 O(log(arr.length)) 复杂度。对于大规模数组，线性扫描的效率远低于二分查找。

4. 最优解：基于二分查找的峰值定位

要满足 O(logN) 的时间复杂度，我们必须采用二分查找。关键在于如何根据 mid 位置的元素，正确地缩小搜索区间。

核心思想：

利用山脉数组的单调性，我们可以通过比较 arr[mid] 和 arr[mid+1] 来判断 mid 位于上升坡还是下降坡，从而确定峰值的大致方向。

如果 arr[mid] 这意味着 mid 位于山脉的上升坡上。因为数组是严格递增的，mid 肯定不是峰值，峰值一定在 mid 的右侧。因此，我们将搜索范围的下界 low 更新为 mid + 1。
如果 arr[mid] > arr[mid+1]： 这意味着 mid 位于山脉的下降坡上，或者 mid 本身就是峰值。在这种情况下，峰值可能就是 mid，也可能在 mid 的左侧。因此，我们将搜索范围的上界 high 更新为 mid。

算法步骤：

初始化 low = 0 和 high = arr.length - 1，定义完整的搜索区间。
使用 while (low
在循环内部，计算 mid = low + (high - low) / 2，以防止整数溢出（相比 (low + high) / 2 更安全）。
根据 arr[mid] 与 arr[mid+1] 的比较结果更新 low 或 high：
- 如果 arr[mid]
- 如果 arr[mid] > arr[mid+1]，则 high = mid。
当循环结束时，low（或 high）的值即为山脉数组的峰值索引。

示例代码：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        // 搜索范围可以覆盖整个数组。
        // 因为题目保证了峰值不在两端，所以实际峰值会在 [1, arr.length - 2] 区间内。
        // 但为了通用性，我们通常将 high 初始化为 arr.length - 1。
        int high = arr.length - 1; 

        // 循环条件：当 low == high 时，表示找到了峰值索引
        while (low < high) { 
            int mid = low + (high - low) / 2; // 计算中间索引，防止溢出

            // 如果 mid 位于上升坡 (arr[mid] < arr[mid+1])
            // 峰值一定在 mid 的右侧，mid 肯定不是峰值
            if (arr[mid] < arr[mid + 1]) {
                low = mid + 1; 
            }
            // 如果 mid 位于下降坡 (arr[mid] > arr[mid+1])
            // 或者 mid 就是峰值
            // 峰值可能就是 mid，也可能在 mid 的左侧