Java递归实现二分查找始终返回-1问题排查

你的代码核心问题是递归调用时没有返回结果，不管递归过程中有没有找到目标值，最后都会执行到方法末尾的return -1，所以永远返回-1。另外你调用时传入的high参数是array.length，这会导致第一次计算mid时可能超出数组索引范围（数组索引最大是array.length-1）。

问题代码的关键错误点 #

在else分支里，你修改了high或low后调用了递归方法，但没有把递归方法的返回值传递出去：

if (middleNumber > key) {
    high = mid - 1; 
    recursiveBinarySearch(array, key, high, low); // 这里没return
}

else {
    low = mid + 1; 
    recursiveBinarySearch(array, key, high, low); // 这里也没return
}

修复后的代码 #

public static int recursiveBinarySearch(int array[], int key, int high, int low) {
    // 先判断查找边界，避免无效计算
    if (low > high)
        return -1;
        
    int mid = (high + low) / 2;
    int middleNumber = array[mid];
        
    if (key == middleNumber )
        return mid; 
    else if (middleNumber > key) {
        // 返回递归调用的结果
        return recursiveBinarySearch(array, key, mid - 1, low);
    } else {
        // 返回递归调用的结果
        return recursiveBinarySearch(array, key, high, mid + 1);
    }
}

调用时的注意点 #

调用时high要传入array.length - 1，而不是array.length，否则第一次计算mid时可能越界：

int[] array = {1, 6, 7, 9, 11 , 16};
// 正确调用
int result = recursiveBinarySearch(array, 7, array.length - 1, 0);
System.out.println(result); // 输出2，对应正确索引

内容的提问来源于stack exchange，提问作者Areeyoka John