请用递归实现找到数组中的最大(最小)值: 1)使用在第k个元素和剩余n-k个元素中的最大(小)值比较 2)使用数组的左半边和右半边比较。
时间: 2024-10-06 15:06:38 浏览: 14
当然可以。这两种方法都可以通过递归来实现数组的最大或最小值。让我们分别来看:
**1)分治法(二分查找+递归):**
这种方法通常用于寻找有序数组的中间元素,但我们可以将其扩展到找最大值或最小值。假设我们有一个整数数组`arr[]`,我们将递归地比较前半部分(索引小于`n/2`)和后半部分(索引大于等于`n/2`)的当前最大值。
```java
public class Main {
public static int findMax(int[] arr, int start, int end) {
if (start == end) { // base case: single element
return arr[start];
} else if (end - start == 1) { // two elements
return Math.max(arr[start], arr[end]);
} else {
int mid = (start + end) / 2;
return Math.max(findMax(arr, start, mid), findMax(arr, mid + 1, end));
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7};
System.out.println("Maximum value is: " + findMax(arr, 0, arr.length - 1));
}
}
```
**2)递归遍历:**
这种方法更直接,我们从第一个元素开始,每次递归调用都比较当前元素与已经找到的全局最大值或最小值。
```java
public class Main {
private static int max = Integer.MIN_VALUE; // or initialize with array[0] for min
private static int min = Integer.MAX_VALUE;
public static void findMinMaxRecursively(int[] arr, int index) {
if (index < arr.length) {
if (arr[index] > max) {
max = arr[index];
} else if (arr[index] < min) {
min = arr[index];
}
findMinMaxRecursively(arr, index + 1); // Move to the next element
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7};
findMinMaxRecursively(arr, 0);
System.out.println("Minimum value is: " + min);
System.out.println("Maximum value is: " + max);
}
}
```