java - 使用递归java的二进制搜索

Question

我正在尝试编写一种方法，仅使用二进制搜索和递归即可找到所需数字的索引。这是我写的方法:

public static int binSearch_r (int[] data, int value, int from, int to)
    {
        if (from <= to)
        {
            int middle = (from+to)/2;
            if (data[middle] > value)
            {
                binSearch_r(data, value, from, middle - 1);
            }
            else if (data[middle] < value)
            {
                binSearch_r(data, value, middle+1, to);
            }
            else
            {
                return middle;
            }
        }
        return -1;
    }

data 是输入的原始数组，value 是我要查找的数字，from 是数组最左边的索引，to 是数组最右边的索引。

我测试此方法所用的数组只是 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}。但是，当我将值设置为 9，将初始“from”设置为 0 并将初始“to”设置为 array.length-1 时，我收到 -1 而不是所需的索引。对于我为值设置的任何数字都会发生这种情况。我做错了什么？

Answer 1

如果您不熟悉递归，this是很好的资源，可以在 Java 上下文中很好地解释它。

在递归二分查找中，如果找不到正确的索引，递归方法会减少查找空间。随着搜索空间的减少，该方法将调用自身以在这个减少的空间内找到索引。每个递归调用都期望返回一个值。

public static int binSearch_r (int[] data, int value, int from, int to) {
    if (from <= to) {
        int middle = (from+to)/2;

        if (data[middle] > value) {
            return binSearch_r(data, value, from, middle - 1);
        } else if (data[middle] < value) {
            return binSearch_r(data, value, middle+1, to);
        }
        return middle;            
    }
    return -1;
}

(从评论转移到回答问题)