山峰数组峰值索引查找问题排查：二分查找实现错误分析

问题描述 #

实现山峰数组峰值索引的二分查找时，输入数组[0,2,1,0]，代码输出结果为2，与预期结果1不符，以下是出错的Java代码：

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;
        }return mid;       
    }
}

错误原因分析 #

1. 逻辑运算符误用：代码中使用了单竖线|（按位或）而非双竖线||（逻辑或）。按位或会强制执行所有表达式，不仅逻辑判断错误，还可能引发数组越界；逻辑或具备短路特性，能避免不必要的计算。
2. 二分方向判断错误：当arr[mid-1] > arr[mid]时，说明峰值在左侧区间，应将high设为mid-1，而非把low设为mid+1；反之，若arr[mid+1] > arr[mid]，则峰值在右侧区间，需将low设为mid+1。原代码的区间调整逻辑完全颠倒。
3. 峰值判断条件冗余且不准确：根据题目定义，山峰数组严格递增后严格递减，峰值不可能出现在数组两端（0或arr.length-1），因此无需判断mid==0或mid==high；同时应使用严格大于>而非>=，符合题目中严格增减的定义。

修正后的代码 #

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2; // 避免low+high溢出
            if (arr[mid] < arr[mid + 1]) {
                // 处于递增区间，峰值在右侧
                low = mid + 1;
            } else {
                // 处于递减区间，峰值在左侧（含mid）
                high = mid;
            }
        }
        // 循环结束时low==high，即为峰值索引
        return low;
    }
}

修正说明 #

• 简化循环条件：使用low < high，无需处理low<=high的边界情况，逻辑更简洁。
• 调整区间判断：通过比较arr[mid]和arr[mid+1]直接确定峰值所在区间，符合山峰数组严格增减的特性。
• 避免整数溢出：用low + (high - low)/2替代(low+high)/2，防止low和high过大时的溢出问题。

题目定义 #

山峰数组arr的定义为：

• arr.length >= 3
• 存在索引i（0 < i < arr.length - 1），满足arr[0] < arr[1] < ... < arr[i-1] < arr[i]，且arr[i] > arr[i+1] > ... > arr[arr.length-1]
  要求实现的算法时间复杂度为O(log(arr.length))

内容的提问来源于stack exchange，提问作者Jack Sparrow