递归算法来寻找数组中的最小元素

Question

我有一些递归算法的伪代码，可以找到数组中的最小数。

这是算法。

Min(A[0..n - 1]) 
If n = 1 return A[0] 
else 
{ 
    temp <-- Min(A[0..n - 2]) 
    if temp <= A[n - 1] 
    return temp 
    else return A[n - 1] 
} 

一部分我不理解该伪代码是行 “临时< - 最小（A [0..N - 2]）”。具体来说，为什么在递归调用中“n - 2”而不是“n - 1”？

我的另一个问题是我将如何在代码中实现该行。我正在使用Java。

在此先感谢您的帮助。

Answer 1

因为你的数组索引从0到n-1（含）。你需要递减一个小数组的子数组，因此n-2。

Answer 2

我的另一个问题是我将如何在代码中实现该行。

如果您使用的是数组。

// create an array with one less element. 
A a2 = new A[a.length-1]; 
// copy the elements 
System.arrayCopy(a,0,a2,0,a2.length); 

如果您使用的是列表

List<A> a2 = a.subList(0, a.length-1); 

Answer 3

你的第一个问题：

，因为你使用的是递归算法，为了解决这个问题，首先要解决的与较小尺寸相同的问题。在这个伪代码中，为了找到长度为n的数组的最小值，首先找到大小为n-1的相同数组的最小值，然后将最小值与第n个元素进行比较。你的数组的索引从0到n-1（这会使它的长度= n），所以为了递归调用，你必须调用从索引0到n-2（n-1个元素）的数组。

你的第二个问题： 这是我将如何实现在Java代码：每次改乘需要是一个更接近递归的结束时间

public class Minimum { 
    public Minimum(int[] A) { 
    findMin(A, 0, A.length-1); 
} 

public int findMin(int [] A, int start, int end){ 
    if (start== end-1) 
     return A[0]; 
    else{ 
     int temp=findMin(A, start, end-1); 
     if (temp<=A[end]) 
      return temp; 
     else 
      return A[end]; 
    } 
} 

}