山脉数组峰值索引查找：从线性扫描到高效二分查找

public class Solution {
    public static int peakIndexInMountainArray(int[] arr) {
        // 初始化峰值和峰值索引。
        // 由于题目保证arr.length >= 3，且峰值在0 < i < arr.length - 1，
        // 可以从arr[0]开始，或者确保peakValue初始值足够小。
        // 这里的实现从0开始，适用于所有非负数的情况。
        int peakValue = 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("示例 1: " + peakIndexInMountainArray(new int[]{0,1,2}));        // 2 (峰值是2，索引2)
        System.out.println("示例 2: " + peakIndexInMountainArray(new int[]{0,1,0}));        // 1 (峰值是1，索引1)
        System.out.println("示例 3: " + peakIndexInMountainArray(new int[]{0,2,1,0}));      // 1 (峰值是2，索引1)
        System.out.println("示例 4: " + peakIndexInMountainArray(new int[]{0,10,5,2}));     // 1 (峰值是10，索引1)
        System.out.println("示例 5: " + peakIndexInMountainArray(new int[]{0,100,500,2}));  // 2 (峰值是500，索引2)
    }
}

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        // high的初始值可以设置为arr.length - 1。
        // 根据山脉数组的定义，峰值不会是最后一个元素（arr.length - 1），
        // 且 mid + 1 在循环内部是安全的，不会越界，因为 high 最终会收敛到峰值索引，
        // 而峰值索引小于 arr.length - 1。
        int high = arr.length - 1; 

        // 当 low < high 时继续循环。
        // 最终 low 和 high 会汇合到峰值索引。
        while (low < high) {
            // 计算中间索引，防止 low + high 溢出
            int mid = low + (high - low) / 2; 

            // 如果 mid 位于上升坡 (arr[mid] < arr[mid+1])，
            // 峰值在 mid 的右侧，包括 mid+1。
            if (arr[mid] < arr[mid + 1]) {
                low = mid + 1;
            } 
            // 如果 mid 位于下降坡 (arr[mid] > arr[mid+1])，
            // 或者 mid 就是峰值。
            // 峰值在 mid 或 mid 的左侧。
            else { // arr[mid] > arr[mid + 1]
                high = mid;
            }
        }
        // 循环结束时，low（或 high，因为它们相等）即为峰值索引
        return low; 
    }
}