在山脉数组中查找峰值索引：O(log N) 二分查找详解

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;
            // 错误的判断逻辑和边界处理
            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; // 这里的 high 更新不应是无条件的
        }
        return mid;
    }
}

public class Solution {
    /**
     * 在山脉数组中查找峰值索引，时间复杂度为 O(log N)。
     *
     * @param arr 山脉数组
     * @return 峰值索引
     */
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        // 搜索区间可以设定为 [0, arr.length - 1]
        // 也可以更精确地设定为 [1, arr.length - 2]，因为峰值不可能在两端
        int high = arr.length - 1; 

        // 当 low == high 时，循环结束，此时 low (或 high) 就是峰值索引
        while (low < high) {
            int mid = low + (high - low) / 2;

            // 如果 arr[mid] 小于 arr[mid+1]，说明 mid 在上升坡
            // 峰值在 mid 的右侧，更新 low
            if (arr[mid] < arr[mid + 1]) {
                low = mid + 1;
            } 
            // 如果 arr[mid] 大于 arr[mid+1]，说明 mid 在下降坡或 mid 就是峰值
            // 峰值在 mid 或 mid 的左侧，更新 high
            else { // arr[mid] > arr[mid+1]
                high = mid;
            }
        }
        // 循环结束时，low 和 high 相等，指向峰值索引
        return low;
    }

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

public class LinearScanSolution {
    /**
     * 在山脉数组中查找峰值索引，时间复杂度为 O(N)。
     *
     * @param arr 山脉数组
     * @return 峰值索引
     */
    public static int peakIndexInMountainArray(int[] arr) {
        int peakValue = arr[0]; // 假设第一个元素是初始峰值
        int peakIndex = 0;
        for (int i = 1; i < arr.length; i++) { // 从第二个元素开始遍历
            int value = arr[i];
            if (value > peakValue) {
                peakValue = value;
                peakIndex = i;
            } else {
                // 如果当前值不大于peakValue，且之前是递增，现在开始递减，
                // 那么当前的peakValue就是峰值。
                // 由于山脉数组的特性，一旦开始下降，就不会再上升，
                // 所以可以直接返回当前的 peakIndex。
                // 优化：对于山脉数组，一旦遇到下降趋势，就可以确定峰值已过
                return peakIndex; 
            }
        }
        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
    }
}