问题

求一个随机数组的最大值和最小值。

排序

可以首先对数据排序，然后获取。

本文暂时不考虑排序的情况，前提是数组乱序。

常见方式

遍历

最简单的就是直接遍历数组。

如何从n个数里找到最大值与最小值？

很容易想到，用一个循环找到最大值和最小值，就能搞定。

(int, int) find_max_min(int arr[n]){
    int max = -infinite;
    int min = infinite;

    for(int i=0; i<n; i++){
        if(arr[i]>max)
            max=arr[i];
        if(arr[i]<min)
            min=arr[i];
    }

    return (max, min);
}

算法复杂度：

这里，需要执行 2*(n-1)=2n-2 次比较。

分治法

当然，还能不能更快呢？

本篇主要想讲解一下分治法。

思路

分治法或许可以派上用场，分治法的思路是：

(1)把大规模拆分成小规模；

(2)小规模分别求解；

(3)小规模求解之后，再综合求解大规模；

看能不能往这个例子里套用：

(1)将 arr[0,n] 分为 arr[0,n/2] 和 arr[n/2,n]；

(2)每个子数组分别求解最大值和最小值；

(3)两个子数组的最大值里再取最大值，两个子数组的最小值里再取最小值，就是最终解；

伪代码

伪代码大概是这样：

(int, int) find_max_min(int arr[0,n]){

    // 递归左半区
    (max1, min1) = find_max_min(arr[0, n/2]);

    // 递归右半区
    (max2, min2) = find_max_min(arr[n/2, n]);

    // 再计算两次
    max = max1>max2?max1:max2;
    min = min1<min2?min1:min2;

    return (max, min);
}

画外音，实际的递归代码要注意：

(1)入参不是0和n，而是数组的下限和上限；

(2)递归要收敛，当数组的上下限相差1时，只比较一次，直接返回max和min，而不用再次递归；

时间复杂度

分治法之后，时间复杂度是多少呢？

当只有2个元素时，只需要1次计算就能知道最大，最小值

当有n个元素时，

(1)递归左半区；

(2)递归右半区；

(3)再进行两次计算；

f(2)=1;【式子A】

f(n)=2*f(n/2)+2;【式子B】

求解递归式子，得到：

f(n)=1.5n-2;

证明如下

证明过程如下：

【式子B】不断展开能得到：

f(n)=2*f(n/2)+2;【式子1】

f(n/2)=2*f(n/4)+2;【式子2】

f(n/4)=2*f(n/8)+2;【式子3】

…

f(n/2^(m-1))=2*f(2^m)+2;【式子m】

通过这m个式子的不断代入，得到：

f(n)=(2^m)*f(n/2^m)+2^(m+1)-2;【式子C】

由于f(2)=1【式子A】;

即【式子C】中n/2^m=2时，f(n/2^m)=f(2)=1;

此时n=2^(m+1)，代入【式子C】

即f(n)=n/2 + n -2 = 1.5n-2;

参考资料

再问我最大值最小值了

求数组最大值