OJ題解：數列有序 - 有序陣列插入元素

題目要求

已有 n (≤100) 個整數按升序排列，插入新整數 m 後保持有序。多組測試資料，n=m=0 結束。

演算法對比

優化版：二分查找 + 後移

#include <stdio.h>

int main() {
    int n, m, a[101], i, pos;
    while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
        for (i = 0; i < n; i++) scanf("%d", &a[i]);
        // 二分查找插入位置
        int L = 0, R = n;
        while (L < R) {
            int mid = (L + R) / 2;
            if (a[mid] < m) L = mid + 1;
            else R = mid;
        }
        pos = L;
        // 後移元素
        for (i = n; i > pos; i--) a[i] = a[i-1];
        a[pos] = m;
        // 輸出
        for (i = 0; i <= n; i++) {
            printf("%d", a[i]);
            if (i < n) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

串流版 (不儲存陣列)

while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
    int printed = 0, x;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (!printed && x > m) { printf("%d ", m); printed = 1; }
        printf("%d", x);
        if (i < n-1 || !printed) printf(" ");
    }
    if (!printed) printf("%d", m);
    printf("\n");
}

範例

輸入: 3 3 / 1 2 4
插入位置: 索引2 (0-based)
結果: 1 2 3 4 ✓