二分查找问题：找到目标值后函数为何不终止仍返回-1

核心问题出在递归调用时没有返回递归函数的结果，导致找到目标值的分支返回的正确索引无法传递到上层调用，最终上层代码会继续执行到return -1。

看你代码里的这两段：

BS(arr, target, first, last); // 这里调用了递归，但没返回结果

不管是目标值在左半区还是右半区的递归调用，你都只是执行了函数，但没有把递归得到的结果返回给上层。举个例子：当递归到某一层找到目标值7时，这一层会return mid，但它的上层调用因为没写return BS(...)，所以会继续执行System.out.println("test")，然后走到方法末尾的return -1，把正确的返回值覆盖了。

修复方法 #

在所有递归调用的地方加上return，把递归结果传递回去：

public class BinarySearch {

    public static int BS(int[] arr, int target, int first, int last) {
        if(first != last) {
            int mid = first + (last - first)/2;
            System.out.println("arr[mid] = "+arr[mid]);
            if(arr[mid] != target) {
                if(target < arr[mid]) {
                    last = mid - 1;
                    System.out.println("last is "+last);
                    return BS(arr, target, first, last); // 新增return
                }else {
                    first = mid + 1;
                    System.out.println("first is "+first);
                    return BS(arr, target, first, last); // 新增return
                }
            }else {
                System.out.println("Found!");
                return mid;
            }
            System.out.println("test"); // 修复后找到目标值时不会走到这里
        }
    
        if(arr[first] == target) return first;
        System.out.println("Not found!");
        return -1;
    }
    
    public static void main(String[] args) {
        int[] test = {0,1,2,4,6,7,9,10};
        int result = BS(test, 7, 0, test.length-1);
        System.out.println(result); // 现在会输出正确的索引5
    }

}

为什么这样修复？ #

递归调用本质是嵌套的函数调用，每一层的返回值需要传递给上一层。如果不写return，上层调用会忽略递归分支的结果，继续执行后续代码，最终走到默认的return -1，这就是你看到错误结果的原因。

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