数组最大值和最小值

继《分治算法》一节后，本节我们尝试用“分而治之”的思想解决“找数组中的最大值和最小值”问题。

所谓“找数组中的最大值和最小值”问题，是指在长度为 n 的数字序列中找到最大的数和最小的数。

普通算法

解决这个问题，我们最常想到的算法是：将序列中首个数字分别赋值给两个变量 max 和 min，从第 2 个数字开始遍历整个序列，如果遍历到的数字比 max 大，将其赋值给 max，如果遍历到数字比 min 小，将其赋值给 min。整个序列遍历完成后，max 记录的是序列中最大的数字，min 记录的是序列中最小的数字。

如下为上述算法对应的伪代码：

输入 arr[n]                             // 输入 n 个数字
max <- arr[1] , min <- arr[1]   // 将第 1 个数字分别赋值给 max（表示最大值）和 min（表示最小值）
for i<- 2 to n:                     // 从第 2 个数字开始遍历
    if arr[i]>max:                    // 如果 max 小于遍历到的数字，则更新 max 的值
        max <- arr[i]
    if arr[i]<min:                     // 如果 min 小于遍历到的数字，则更新 min 的值
        min <- arr[i]
print max , min                  // 输出 max 和 min 的值

为了找到最大值和最小值，该算法实现过程中进行了大量的数值比较操作，对于一个长度为 n 的序列来说，数字间的比较操作共进行了2*n-2次。相比该算法，采用“分而治之”的思想解决这个问题，比较次数将大大减少。

分治算法

如下是采用分治算法解决“找数组中最大值和最小值”的伪代码：

输入 arr[n]                                                                     // 输入 n 个数字
max_min(x , y) :                                                             // 设计一个递归函数，[x , y] 用来限定查找最大数和最小数的范围
    if y-x ≤ 1 :                                                                 // 如果 y-x 的值小于等于 1，则比较 arr[x] 和 arr[y] 的值，大的就是最大值，小的就是最小值  
        return max(arr[x] , arr[y]) ,  min(arr[x] , arr[y])
    else :
        max1 , min1 = max_min (x , ?(x+y)/2? )                   // 将 [x , y] 区域划分为 [x , ?(x+y)/2? ] 和 [ ?(x+y)/2+1? , y] 两个区域，分别求出两个区域内各自的最大值和最小值
        max2 , min2 = max_min( ?(x+y)/2+1? , y)
    return max(max1 , max2) , min(min1 , min2)          // 比较两个区域的最大值和最小值，最终找出 [x , y] 中的最大值和最小值

显然，以上伪代码是以递归的方式实现的，整个实现思路为：

1. 将 arr 序列中的 [x , y] 区域等分为 [x , ?(x+y)/2? ] 和 [ ?(x+y)/2+1? , y] 这两个小区域，各自找到两个小区域内的最大值和最小值，最终通过比较两个最大值和两个最小值，即可找出 [x , y] 整个区域内的最大值和最小值；

2. 对于 [x , ?(x+y)/2? ] 区域，继续划分，直至各个小区域内的数字个数小于等于 2；同样 [ ?(x+y)/2+1? , y] 区域也做同样的处理。

3. 通过第 2 步，所有的小区域内的数字个数都小于等于 2，比较 2 个数字的大小是非常容易实现的，最终即可求出整个 [x , y] 区域内的最大值和最小值。

以 [1,3,5,4,2,6,0,9] 为例，下图给您演示了分治算法“找数组中最大值”的过程：

图 1 分治法找最大值

如图所示，借助“分而治之”的思想，我们将“求 [1,3,5,4,2,6,0,9] 中最大值和最小值”的问题，划分成了分别“求 [1 , 3]、[5 , 4]、[2 , 6]、[0 , 9] 中最大值和最小值”的问题， 极大地简化了问题的难度。

相比普通算法，采用分治法解决此问题只需要比较3*n/2-2次（由于涉及很复杂的数学推理过程，这里不做详细解释）。

结合图 1，如下为分治法实现“找序列中最大值”的 C 语言程序：

#include <stdio.h>//自定义函数，其中 [left,right] 表示 arr 数组中查找最大值的范围int get_max(int arr[8], int left, int right) {int max1 = 0, max2 = 0, middle = 0;//如果数组不存在if (arr == NULL) {return  -1;}//如果查找范围中仅有一个数字if (right - left == 0) {return arr[left];}//如果查找范围中仅有 2 个数字，则直接比较即可if (right - left <= 1) {if (arr[left] >= arr[right]) {return arr[left];}return  arr[right];}//等量划分成 2 个区域middle = (right - left) / 2 + left;//得到左侧区域中的最大值max1 = get_max(arr, left, middle);//得到右侧区域中的最大值max2 = get_max(arr, middle + 1, right);//比较左、右两侧的最大值，找到 [left,right] 整个区域的最大值if (max1 >= max2) {return  max1;}else {return max2;}}int main() {int arr[8] = { 1,3,5,4,2,6,0,9 };int max = get_max(arr, 0, 7);printf("最大值：%d", max);return 0;}

如下为分治法实现“找序列中最大值”的 Java 程序：

public class Demo {public static int get_max(int [] arr,int left,int right) {//如果数组不存在或者数组内没有元素if (arr == null || arr.length == 0) {return 0;}//如果查找范围中仅有 2 个数字，则直接比较即可if(right - left <=1) {if(arr[left] >= arr[right]) {return arr[left];}return arr[right];}//等量划分成 2 个区域int middle = (right-left)/2 + left;int max_left = get_max(arr,left,middle);int max_right = get_max(arr,middle+1,right);if(max_left >= max_right) {return max_left;}else {return max_right;}}public static void main(String[] args) {int [] arr = new int[] { 1,3,5,4,2,6,0,9 };int max = get_max(arr,0,7);System.out.println("最大值："+max);}}

如下为分治法实现“求序列中最大值”的 Python 程序：

def get_max(arr,left,right):#列表中没有数据if len(arr) == 0:return 0#如果查找范围中仅有 2 个数字，则直接比较即可if right - left <= 1:if arr[left] >= arr[right]:return arr[left]return arr[right]#等量划分成 2 个区域middle = int((right-left)/2 + left)max1 = get_max(arr,left,middle)max2 = get_max(arr,middle+1,right)if max1 >= max2:return max1else:return max2arr = [1,3,5,4,2,6,0,9]max = get_max(arr,0,7)print("最大值：",max,sep='')

以上代码的输出结果均为：

最大值：9

读者可根据伪代码以及以上给出的实现代码，尝试编写出用分治法实现“找数组中最小值”的代码。