問題

在長度為 n 的整數數組中同時找出最大值與最小值，最少需要多少次比較？

方案演進

方案一：獨立遍歷（2n 比較）

int max = a[0], min = a[0];
for (int i = 1; i < n; ++i) {
    if (a[i] > max) max = a[i];
    if (a[i] < min) min = a[i];
}
// 比較次數：2(n-1) ≈ 2n

方案二：分組交換（1.5n 比較，破壞原數組）

1. 相鄰兩兩分組，共 n/2 組
2. 組內比較，大的放偶數索引，小的放奇數索引（n/2 次）
3. 偶數索引中找最大（n/2 - 1 次），奇數索引中找最小（n/2 - 1 次）
4. 總計：n/2 + n/2 - 1 + n/2 - 1 = 1.5n - 2

for (int i = 0; i+1 < n; i += 2) {
    if (a[i] < a[i+1]) std::swap(a[i], a[i+1]); // 大→偶數位
}
int max = a[0], min = a[1];
for (int i = 2; i < n; i += 2) if (a[i] > max) max = a[i];
for (int i = 3; i < n; i += 2) if (a[i] < min) min = a[i];

方案三：分組不交換（1.5n 比較，保持原數組）

組內比較後，直接用較大值更新 max，較小值更新 min，無需移動元素。

int max = a[0], min = a[0];
for (int i = 0; i+1 < n; i += 2) {
    int larger, smaller;
    if (a[i] > a[i+1]) { larger = a[i]; smaller = a[i+1]; }
    else { larger = a[i+1]; smaller = a[i]; }
    if (larger > max) max = larger;
    if (smaller < min) min = smaller;
}
// 若 n 為奇數，單獨處理最後一個元素
if (n % 2) {
    if (a[n-1] > max) max = a[n-1];
    if (a[n-1] < min) min = a[n-1];
}
// 比較次數：⌈1.5n⌉ - 2

方案四：分治遞歸（1.5n 比較）

遞歸分解為左右半部，合併時比較兩個 max 取大、兩個 min 取小（2 次比較）。遞歸關係 T(n) = 2T(n/2) + 2，解得 T(n) = 1.5n - 2（n 為 2 的冪時）。

struct MinMax { int min, max; };
MinMax findMinMax(const std::vector<int>& a, int l, int r) {
    if (l == r) return {a[l], a[l]};
    if (l + 1 == r) {
        return {std::min(a[l], a[r]), std::max(a[l], a[r])};
    }
    int mid = (l + r) >> 1;
    auto left = findMinMax(a, l, mid);
    auto right = findMinMax(a, mid+1, r);
    return {std::min(left.min, right.min), std::max(left.max, right.max)};
}

擴展：尋找第二大元素

方法一：雙變量單遍歷（最多 2n 比較）

int max1 = a[0], max2 = INT_MIN;
for (int i = 1; i < n; ++i) {
    if (a[i] > max1) { max2 = max1; max1 = a[i]; }
    else if (a[i] > max2) { max2 = a[i]; }
}

方法二：快速選擇 + 掃描（平均 O(n)）

1. 用 `nth_element` 或手寫 partition 找到第 2 大位置（平均 O(n)）
2. 在前 2 個元素中找最大（1 次比較）

比較次數：最好 ~n，最壞 ~n²（可用中位數中位數保證 O(n)）。

方法三：錦標賽法（n + log n - 2 比較，最優）

兩兩比較構建冠軍樹，冠軍參與的比較對手中找最大即為亞軍。需額外 O(n) 空間記錄比較路徑。

總結