java - 如何在数组递归方法中找到最小值？

Question

public static int findMin(int[] numbers, int startIndex, int endIndex) {
    if (startIndex == endIndex){
        return numbers[startIndex];
    }
    else {
        int midIndex = (startIndex + endIndex) / 2;
        int leftMin = findMin(numbers, startIndex, midIndex);
        int rightMin = findMin(numbers, midIndex + 1, endIndex);
        if (leftMin < rightMin)
            return leftMin;
        else
            return rightMin;
    }
}

我真的很难理解这个 find min 递归。此递归方法查找数组中的最小数字。

我是这么理解的

假设我有一个数组 5, 3 , -5, 8，startIndex 为 0，endIndex 为 3

第一次，midIndex = (0+3)/2 =1。所以它除以 3 和 -5 之间。

然后转到 findMin，因此它将 Array, 0, 1 传回给 findMin。

然后，midIndex = (0+1)/2 = 0。并将 Array, 0, 0 传回给 findMin。

由于 startIndex 0 = endIndex 0，返回数字[startIndex](是 5？)。

我真的不明白这个方法是如何找到最小数字的。既然startIndex始终为0，为什么还需要返回numbers[startIndex]？

Answer 1

这是代码实现的总体思路:

要找到数组的最小元素，我们可以找到数组每一半的最小值，然后取这两个数字的最小值。

我们如何找到每一半的最小值？我们只是使用相同的技术将其分成四等分。

最终我们会问自己单个元素的最小元素是什么，当然就是那个元素。

图像中显示的算法实现了这个配方。