C 語言陣列尋找最大最小值：單趟掃描雙向更新法

C 語言陣列尋找最大最小值：單趟掃描雙向更新法

最佳演算法

#include <stdio.h>

void find_min_max(const int arr[], int len, int *min, int *max) {
    *min = *max = arr[0];
    for (int i = 1; i < len; ++i) {
        if (arr[i] < *min) *min = arr[i];
        if (arr[i] > *max) *max = arr[i];
    }
}

int main() {
    int arr[10];
    printf("輸入 10 個整數: ");
    for (int i = 0; i < 10; ++i) scanf("%d", &arr[i]);
    int min, max;
    find_min_max(arr, 10, &min, &max);
    printf("最小值: %d, 最大值: %d\n", min, max);
    return 0;
}

複雜度分析

• 時間：O(n)，單趟遍歷。
• 空間：O(1)，常數額外空間。
• 比較次數：2(n-1) 次。更優的「成對比較法」可減至 1.5n 次 (先兩兩比較，再分別與極值比)。

成對比較法 (進階)

void find_min_max_pair(const int a[], int n, int *min, int *max) {
    if (n % 2) *min = *max = a[0], n--;
    else { *min = a[0]<a[1]?a[0]:a[1]; *max = a[0]>a[1]?a[0]:a[1]; n -= 2; }
    for (int i = n%2; i < n; i += 2) {
        int small = a[i]<a[i+1]?a[i]:a[i+1];
        int large = a[i]>a[i+1]?a[i]:a[i+1];
        if (small < *min) *min = small;
        if (large > *max) *max = large;
    }
}

教學建議先掌握單趟雙向更新，理解後再學成對比較優化。