尋找一個(gè)數(shù)組中的最大和最小數(shù)

工作一段快兩年了，感覺之前學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法基本忘得差不多了，最近一段時(shí)間準(zhǔn)備復(fù)習(xí)一下相關(guān)知識。

有一個(gè)求數(shù)組中最大和最小數(shù)的題目，基本的思路是遍歷一遍數(shù)組，然后每個(gè)一個(gè)元素都和最大值和最小值比較，時(shí)間復(fù)雜度是2(N-1)或2N。

比較簡單的一種減少復(fù)雜度的方法是把數(shù)組的元素兩兩分組比較，然后較大的數(shù)和max比較，較小的數(shù)和min比較，這種實(shí)現(xiàn)方法的時(shí)間復(fù)雜度是1.5N。

還有一種是采用分治法，比較次數(shù)也是1.5N，思路是將數(shù)組一分為二，分別獲取兩個(gè)子數(shù)組的最大和最小值，然后進(jìn)行取兩個(gè)子數(shù)組中較小的最小值和較大的最大值。

O(N) = (N/2 + N/4 + … + N/2^(log2(N))) = 3N/2 ?

#include <cstdio>

    void max_min(int a[], int begin, int end, int *max, int *min) {
        if (end == begin) {
            *max = a[begin];
            *min = a[end];

            return;
        }
        int l_max, r_max;
        int l_min, r_min;
        max_min(a, begin, begin + (end - begin) / 2, &l_max, &l_min);
        max_min(a, begin + (end - begin) / 2 + 1, end, &r_max, &r_min);
        *max = l_max > r_max ? l_max : r_max;
        *min = l_min < r_min ? l_min : r_min;
    }

    int main() {
        int array[] = {5,7,8,9,11,13,45,8,9,23,45,97,3,2,7,14,64};
        int len = sizeof(array) / sizeof(int);
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < len; ++i) {
            if (array[i] > max) {
                max = array[i];
            } else if (array[i] < min){
                min = array[i];
            }
        }
        printf("max:%d min:%d\", max, min);
        int start = -1;
        if (len & 0x1) {
            start = 1;
        } else {
            start = 0;
        }
        for (int i = start; i < len; i+=2) {
            if (array[i] > array[i + 1]) {
                if (array[i] > max) max = array[i];
                if (array[i + 1] < min) min = array[i + 1];
            } else if (array[i] < array[i + 1]) {
                if (array[i] < min) min = array[i];
                if (array[i + 1] > max) max = array[i + 1];
            }
        }
        printf("max:%d min:%d\", max, min);

        max_min(array, 0, len - 1, &max, &min);
        printf("max:%d min:%d\", max, min);

        return 0;
    }