尋找序列最大值與最小值：最優比較次數演算法（3N/2 次比較）

問題與朴素解法

給定長度 N 序列，求最大值與最小值。

• 單獨遍歷兩次：(N-1) + (N-1) = 2N-2 次比較
• 先找最大值（N-1 次），再從剩餘找最小值（N-2 次）：2N-3 次

兩兩分組法：3N/2 次比較

核心觀察：每次取兩個元素 a, b，先比較它們（1 次），大者與當前最大值比（1 次），小者與當前最小值比（1 次），共 3 次比較處理 2 個元素。總比較次數約 3N/2。

處理邊界

• N 為奇數：首元素初始化為最大/最小值，剩餘 N-1（偶數）分組 → 3(N-1)/2 次
• N 為偶數：前兩元素比較初始化（1 次），剩餘 N-2 分組 → 1 + 3(N-2)/2 = 3N/2 - 2 次

C++ 模板實作（支援動態/靜態陣列）

// 動態陣列版本
template <typename T>
void get_max_min(const T* p, size_t n, T& max, T& min) {
    assert(n > 0);
    T cur_max = p[0], cur_min = p[0];
    size_t i = 1;

    // 若 N 為偶數，先處理前兩個元素
    if (n % 2 == 0) {
        if (p[1] < p[0]) { cur_max = p[0]; cur_min = p[1]; }
        else { cur_max = p[1]; cur_min = p[0]; }
        i = 2;
    }

    // 兩兩分組處理
    for (; i + 1 < n; i += 2) {
        T larger, smaller;
        if (p[i+1] < p[i]) { larger = p[i]; smaller = p[i+1]; }
        else { larger = p[i+1]; smaller = p[i]; }
        if (cur_max < larger) cur_max = larger;
        if (smaller < cur_min) cur_min = smaller;
    }

    // 處理剩餘單一元素（N 為奇數時）
    if (i < n) {
        if (cur_max < p[i]) cur_max = p[i];
        else if (p[i] < cur_min) cur_min = p[i];
    }
    max = cur_max; min = cur_min;
}

// 靜態陣列版本（自動推導大小）
template <typename T, size_t N>
void get_max_min(const T (&arr)[N], T& max, T& min) {
    get_max_min(arr, N, max, min);
}

複雜度分析

時間複雜度 O(N)，比較次數為理論下界（證明可參考 CLRS 教科書）。

為何不再分 3、4 個一組？

分 3 個一組需 5 次比較（平均 5/3 ≈ 1.667），分 4 個需 7 次（平均 1.75），皆高於 1.5。兩兩分組在比較模型下為最優。