数组最大值和最小值

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

所谓“找数组中的最大值和最小值”问题，是指在长度为 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,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 max1
    else:
        return max2
arr = [1,3,5,4,2,6,0,9]
max = get_max(arr,0,7)
print("最大值：",max,sep='')

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

最大值：9

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