Java递归实现二分查找返回错误值，求助问题排查与修复

嘿，我看了你的代码，问题主要出在索引映射错误和返回值逻辑混乱上，导致你得到的结果和预期不符。咱们一步步拆解问题：

核心错误点 #

• 局部索引代替全局索引：你每次用Arrays.copyOfRange生成子数组后，递归返回的是这个子数组里的位置，而不是原数组的真实索引。比如找8的时候，第一次拆分出的子数组是[6,7,8,9,10]，在这个子数组里8的索引是2，但原数组里它的索引是7，所以直接返回2就完全错了。
• 返回值类型混淆：当你在数组长度小于2时找到元素，你返回的是item（也就是元素值8）而不是索引，这会导致匹配到元素时返回的是元素值而非位置，进一步混乱了结果。
• 奇偶长度的冗余错误处理：你单独处理了数组长度为奇数的情况，但判断array[splitSize]==item时直接返回splitSize，这也是当前子数组的索引，没有考虑原数组的偏移量，同样会导致索引错误。
• 边界条件缺失：没有处理空数组的情况，如果递归中出现长度为0的数组，访问array[0]会直接抛出异常。

修复方案一：用low/high跟踪原数组范围（推荐） #

这种方式不需要复制数组，既高效又能直接跟踪原数组的索引，是二分查找的标准实现方式：

import java.util.*;
class BinarySearchRecursion{
    // 对外暴露的简洁方法，隐藏递归细节
    static public int searchNum(int[] array, int item){
        return searchRecursive(array, item, 0, array.length - 1);
    }

    // 内部递归方法，用low和high标记当前查找的原数组范围
    static private int searchRecursive(int[] array, int item, int low, int high){
        // 边界：查找范围不存在，说明元素不在数组中
        if (low > high) {
            return -1;
        }
        // 计算中间索引，避免直接(low+high)/2导致的整数溢出
        int mid = low + (high - low) / 2;
        
        if (array[mid] == item) {
            // 找到元素，直接返回原数组的索引
            return mid;
        } else if (item > array[mid]) {
            // 元素在右半区，递归查找右半部分
            return searchRecursive(array, item, mid + 1, high);
        } else {
            // 元素在左半区，递归查找左半部分
            return searchRecursive(array, item, low, mid - 1);
        }
    }

    public static void main(String... args){
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int index = searchNum(arr, 8);
        if(index != -1){
            System.out.println("Number exist at index: " + index);
        } else {
            System.out.println("Number does not exist in the given list.");
        }
    }
}

关键修改说明 #

• 新增searchRecursive方法，用low和high参数跟踪当前在原数组中查找的范围，不需要复制子数组，性能更好。
• 计算中间索引时用low + (high - low)/2，避免了(low+high)/2可能出现的整数溢出问题。
• 明确边界条件：当low > high时，说明元素不存在，直接返回-1。
• 对外的searchNum方法封装了递归细节，调用起来更友好。

修复方案二：保留数组复制，增加偏移量参数 #

如果你想保留原来的数组复制逻辑，可以通过传递偏移量来映射原数组的索引：

import java.util.*;
class BinarySearchRecursion{
    // 内部递归方法，增加offset参数记录子数组在原数组中的起始索引
    static private int searchNum(int[] array, int item, int offset){
        // 处理空数组边界
        if(array.length == 0){
            return -1;
        }
        // 数组长度为1时，判断是否匹配并返回原数组索引
        if(array.length == 1){
            return array[0] == item ? offset : -1;
        }

        int splitSize = array.length / 2;
        int midValue = array[splitSize];
        
        if(midValue == item){
            // 找到元素，返回原数组索引：偏移量+子数组中的位置
            return offset + splitSize;
        } else if(item > midValue){
            // 递归右半部分，偏移量加上当前子数组的拆分长度
            return searchNum(Arrays.copyOfRange(array, splitSize, array.length), item, offset + splitSize);
        } else {
            // 递归左半部分，偏移量不变
            return searchNum(Arrays.copyOfRange(array, 0, splitSize), item, offset);
        }
    }

    // 对外方法，初始偏移量为0
    static public int searchNum(int[] array, int item){
        return searchNum(array, item, 0);
    }

    public static void main(String... args){
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int index = searchNum(arr, 8);
        if(index != -1){
            System.out.println("Number exist at index: " + index);
        } else {
            System.out.println("Number does not exist in the given list.");
        }
    }
}

关键修改说明 #

• 增加offset参数，记录当前子数组在原数组中的起始位置，每次递归时根据子数组的位置更新偏移量。
• 找到元素时返回offset + 子数组中的索引，将局部索引映射回原数组的全局索引。
• 简化了奇偶长度的处理逻辑，不需要单独判断数组长度是否为奇数，splitSize = array.length/2已经能正确处理两种情况。
• 增加了空数组的判断，避免出现数组越界异常。

现在运行这两个修复后的代码，查找8时都会返回正确的索引7，查找89时返回-1，符合预期。

内容的提问来源于stack exchange，提问作者Cosmic Dev