Java递归二分查找代码返回0不符合测试预期，求问题分析

咱们来拆解下为什么你的递归二分查找在测试用例里返回0而不是预期的2。你的代码里有两个关键bug导致了这个问题：

1. 右半部分子数组的范围错误 #

当目标值大于中间元素时，你需要在中间元素右侧的子数组（也就是从midpoint + 1到数组末尾）查找，但你的代码写的是：

Arrays.copyOfRange(arr, midpoint, (arr.length - 1))

这里有两个问题：

• Arrays.copyOfRange的第三个参数是不包含的结束索引，所以arr.length - 1会直接截断数组的最后一个元素。在你的测试用例[1,3,5]中，midpoint=1，这个调用会生成子数组[3]，完全漏掉了要找的5。
• 你还错误地包含了中间元素arr[midpoint]，而右半部分应该从中间元素的下一个位置开始。

正确的右半部分范围应该是：

Arrays.copyOfRange(arr, midpoint + 1, arr.length)

2. 索引偏移量计算错误 #

递归调用子数组时，你需要正确将子数组的索引映射回原数组的索引，你的偏移量计算完全错误：

• 左半部分：当目标值小于中间元素时，左半部分是0到midpoint-1，子数组的索引和原数组的前半部分完全一致，根本不需要加midpoint。你的代码里return midpoint + chopRecursive(...)会导致索引被错误放大，比如查找1时会返回错误的结果。
• 右半部分：当目标值大于中间元素时，右半部分的起始索引是原数组的midpoint+1，所以递归返回的索引需要加上midpoint+1，而不是midpoint。你的测试用例中，第一次递归返回的是-1（因为子数组里没有5），加上midpoint=1后得到0，这就是你看到的错误结果。

另外，你在左半部分加的midpoint ==1判断完全冗余，递归逻辑本身可以处理这种边界情况，反而增加了代码复杂度。

修正后的代码 #

import java.util.Arrays;

public class Chopper {
    static int chopRecursive(int toFind, int[] arr) {
        // 空数组处理
        if (arr.length == 0) return -1;

        int midpoint = arr.length / 2;
        if (arr[midpoint] == toFind) {
            return midpoint;
        } else if (arr[midpoint] > toFind) {
            // 左半部分：直接返回递归结果，无需偏移
            return chopRecursive(toFind, Arrays.copyOfRange(arr, 0, midpoint));
        } else {
            // 右半部分：递归结果需要加上midpoint+1的偏移
            int rightResult = chopRecursive(toFind, Arrays.copyOfRange(arr, midpoint + 1, arr.length));
            return rightResult == -1 ? -1 : (midpoint + 1) + rightResult;
        }
    }
}

修正后的测试流程 #

对于你的测试用例chopRecursive(5, [1,3,5])：

1. 第一次调用：midpoint=1，arr[1]=3 <5，递归调用chopRecursive(5, [5])
2. 第二次调用：midpoint=0，arr[0]=5 ==5，返回0
3. 第一次调用计算：(1+1) +0=2，返回2，完全符合预期。

额外优化建议 #

每次递归调用Arrays.copyOfRange都会创建新数组，性能较差。更优的做法是传递原数组的起始和结束索引作为参数，避免数组复制：

public class Chopper {
    static int chopRecursiveOptimized(int toFind, int[] arr) {
        return chopHelper(toFind, arr, 0, arr.length - 1);
    }

    private static int chopHelper(int toFind, int[] arr, int start, int end) {
        // 查找范围无效，返回-1
        if (start > end) return -1;

        // 计算中间索引，避免整数溢出
        int midpoint = start + (end - start) / 2;
        if (arr[midpoint] == toFind) {
            return midpoint;
        } else if (arr[midpoint] > toFind) {
            // 查找左半部分
            return chopHelper(toFind, arr, start, midpoint - 1);
        } else {
            // 查找右半部分
            return chopHelper(toFind, arr, midpoint + 1, end);
        }
    }
}

内容的提问来源于stack exchange，提问作者Cornel Verster