C++ 求數組最大值與最小值的最優比較次數算法（3n/2 次比較）

問題

在無序數組中同時找出最大值和最小值，最少需要多少次比較？

算法原理：成對比較法

將數組元素兩兩分組，每組先內部比較一次（1 次），得到組內較大者和較小者。然後所有組內較大者中找最大（n/2 - 1 次），所有組內較小者中找最小（n/2 - 1 次）。總比較次數：n/2 + (n/2 - 1) + (n/2 - 1) = 3n/2 - 2（n 為偶數），優於獨立找最大最小的 2n - 2 次。

C++ 代碼實現

#include <iostream>
#include <algorithm>
using namespace std;

void findMinMax(const int a[], int n, int& minVal, int& maxVal) {
    if (n == 0) return;
    int i = 0;
    // 初始化：處理第一對
    if (n % 2 == 1) {
        minVal = maxVal = a[0];
        i = 1;
    } else {
        if (a[0] < a[1]) { minVal = a[0]; maxVal = a[1]; }
        else { minVal = a[1]; maxVal = a[0]; }
        i = 2;
    }
    // 成對處理剩餘元素
    for (; i + 1 < n; i += 2) {
        int localMin, localMax;
        if (a[i] < a[i+1]) { localMin = a[i]; localMax = a[i+1]; }
        else { localMin = a[i+1]; localMax = a[i]; }
        if (localMin < minVal) minVal = localMin;
        if (localMax > maxVal) maxVal = localMax;
    }
    // 若 n 為奇數，最後一個單獨元素單獨比較
    if (i < n) {
        if (a[i] < minVal) minVal = a[i];
        if (a[i] > maxVal) maxVal = a[i];
    }
}

int main() {
    int a[] = {6, -3, -2, 7, -15, 1, 2, 2};
    int mn, mx;
    findMinMax(a, 8, mn, mx);
    cout << "Min: " << mn << ", Max: " << mx << endl; // Min: -15, Max: 7
    return 0;
}

複雜度分析

• 比較次數：⌈3n/2⌉ - 2（理論下界）。
• 時間：O(n)，空間：O(1)。