求解山脉数组的峰值索引：从线性扫描到二分查找

public class Solution {
    public static int peakIndexInMountainArrayLinear(int[] arr) {
        int peakValue = arr[0]; // 初始峰值设为第一个元素
        int peakIndex = 0;

        // 从第二个元素开始遍历，因为第一个元素不可能是峰值（除非数组长度小于3，但山脉数组定义排除此情况）
        // 实际上，从arr[0]开始遍历也可以，只要确保peakValue和peakIndex的初始值正确
        for (int i = 1; i < arr.length; i++) { 
            if (arr[i] > peakValue) {
                peakValue = arr[i];
                peakIndex = i;
            } else {
                // 一旦遇到下降趋势，说明峰值已经找到，因为山脉数组只有一个峰值
                // 进一步优化，可以提前退出循环
                break; 
            }
        }
        return peakIndex;
    }

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

public class Solution {
    public int peakIndexInMountainArrayBinarySearch(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

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

            // 比较 arr[mid] 和 arr[mid+1]
            if (arr[mid] < arr[mid + 1]) {
                // 如果 arr[mid] 小于 arr[mid+1]，说明当前在上升坡
                // 峰值在 mid 的右侧，包括 mid+1
                low = mid + 1;
            } else {
                // 如果 arr[mid] 大于 arr[mid+1]，说明当前在下降坡或者 mid 就是峰值
                // 峰值可能在 mid，也可能在 mid 的左侧
                high = mid;
            }
        }
        // 循环结束时，low == high，这个索引就是峰值
        return low; 
    }

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