拜托，面試别再問我最大值最小值了！！！

如何從n個數裡找到最大值？

很容易想到，用一個循環就能搞定。

int find_max(int arr[n]){

    int max = -infinite;

    for(int i=0; i<n; i++)

        if(arr[i]>max)

            max=arr[i];

    return max;

}

這裡，需要執行n-1次比較。

如何從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;

畫外音，實際的遞歸代碼要注意：

(1)入參不是0和n，而是數組的下限和上限；

(2)遞歸要收斂，當數組的上下限相差1時，隻比較一次，直接傳回max和min，而不用再次遞歸；

分治法之後，時間複雜度是多少呢？

如果你是“架構師之路”的老讀者，能夠輕松求解分治法的時間複雜度分析：

• 當隻有2個元素時，隻需要1次計算就能知道最大，最小值
• 當有n個元素時，

     (1)遞歸左半區；

     (2)遞歸右半區；

     (3)再進行兩次計算；

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

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

求解遞歸式子，得到：

f(n)=1.5n-2;

畫外音，證明過程如下：

【式子B】不斷展開能得到：

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

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

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

...

f(n/2^(m-1))=2f(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;

證明過程很嚴謹，但我知道你沒看懂。

總結，n個數：

• 求最大值，周遊，需要n-1次計算
• 求最大最小值，周遊，需要2n-2次計算
• 求最大最小值，分治，時間複雜度1.5n-2

畫外音：别跳出，文末有作業。

思路比結論重要，希望大家有收獲。

本文轉自“架構師之路”公衆号，58沈劍提供。