java - 如何通过Java中给出的例子来掌握二分查找递归的概念？

Question

最近，我意识到我并没有像我想象的那样得到递归。这就是为什么我试图找到尽可能多的例子来弄清楚，但我很快就被捕获了。

这是简单的二分搜索代码，但我很难理解递归部分。特别是因为我看不出每一步都会发生什么变化。如果在任何时候有+1或-1给任何变量，我可能会得到它，但这里变量是自然传递的，没有任何改变。

public class BinarySearchRecursion {
    public static int binarySearch(int[] array, int value, int start, int end) {
        if ((end - start) <= 1) {
            if (array[start] == value)
                return start;
            if (array[end] == value)
                return end;
            return -1;
        }

        int midPoint = (start + end) / 2;
        if (array[midPoint] > value) {
            return binarySearch(array, value, 0, midPoint);
        } else {
            return binarySearch(array, value, midPoint, end);
        }

    }

    public static void main(String[] args) {
        int[] a = { 4, 9, 10 };
        System.out.println(binarySearch(a, 10, 0, a.length - 1));
    }
}

Answer 1

您似乎被误导了，认为名为 start 的参数在不同的递归调用中是相同的变量 - 但事实并非如此(对于结束)。不同递归调用中特定参数的值之间没有直接联系，即使它具有相同的名称。相反，参数值按位置传递:当您调用 binarySearch 时，您在第三个参数位置写入的任何表达式都将成为 start 的值> 在新的通话中。

因此，如果 array[midPoint] > value 为 true，您将调用 binarySearch(array, value, 0, midPoint)，这实际上是一个错误 - 它是应该是binarySearch(array, value, start, midPoint)。这意味着在新调用中，start 的值将与此调用中的值相同，但 end 的值将是此调用为 中点。否则，您将调用 binarySearch(array, value, midPoint, end)，以便在新调用中，start 的值将为 midPoint code>，并且 end 的值将与此调用中的值相同。

(这适用于所有方法，而不仅仅是递归方法。另外，请注意 array 和 value do 在整个递归过程中保留其值调用，但那是因为您在第一个和第二个参数位置“将它们传递给自己”。)