山脉数组峰值索引查找：从线性扫描到O(logN)二分查找优化

public class Solution {
    public static int peakIndexInMountainArray(int[] arr) {
        int peakValue = 0; // 初始化峰值，通常取数组第一个元素或0
        int peakIndex = 0;

        // 假设数组长度至少为3，且arr[0]总是小于arr[1]，所以可以从0开始比较
        // 更严谨的做法是初始化为arr[0]，peakIndex=0
        if (arr.length > 0) {
            peakValue = arr[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
    }
}

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

        while (low < high) {
            int mid = low + (high - low) / 2;

            // 如果mid在上升段，峰值在mid的右侧
            if (arr[mid] < arr[mid + 1]) {
                low = mid + 1;
            } 
            // 如果mid在下降段，或者mid就是峰值
            // 峰值可能在mid或mid的左侧
            else { 
                high = mid;
            }
        }
        // 当low == high时，找到了峰值索引
        return low; 
    }

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