已有 n (≤100) 個整數按遞增序排列，插入一個整數 m，使新數列仍有序。多組測資，0 0 結束。
由於原陣列已有序，**二分查找** 可在 O(log n) 找到插入位置，再將後續元素整體後移 O(n)，總複雜度 O(n) (受限於移動)。
#include#define MAXN 105 int main() { int n, m; int arr[MAXN]; while (scanf("%d %d", &n, &m) == 2) { if (n == 0 && m == 0) break; for (int i = 0; i < n; i++) scanf("%d", &arr[i]); // 二分查找插入位置: 第一個 >= m 的位置 int left = 0, right = n; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < m) left = mid + 1; else right = mid; } int pos = left; // 插入位置 [0, n] // 從後往前移動元素騰出位置 for (int i = n; i > pos; i--) { arr[i] = arr[i-1]; } arr[pos] = m; n++; // 輸出 for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n-1) putchar(' '); } putchar('\n'); } return 0; }
| 步驟 | 關鍵技術 | 細節 |
|---|---|---|
| 讀取 | scanf 迴圈 | while (scanf("%d %d", &n, &m) == 2) 同時處理 EOF 與 0 0 |
| 查找 | 二分查找 (Lower Bound) | 找第一個 arr[i] >= m 的位置；全 < m 時回傳 n (插尾部) |
| 移動 | 逆向複製 | for (i=n; i>pos; i--) arr[i]=arr[i-1] 避免覆蓋 |
| 插入 | 賦值 | arr[pos] = m |
| 輸出 | 空格分隔、無尾隨空格 | if (i |
// 線性查找插入位置 int pos = 0; while (pos < n && arr[pos] < m) pos++; // 後移邏輯相同
資料量小 (n ≤ 100) 時，線性查找 O(n) 同樣極快，程式碼更簡單，面試/考試常用此法。
| 輸入 | 輸出 |
|---|---|
| 3 3 1 2 4 0 0 | 1 2 3 4 |
| 5 0 1 3 5 7 9 0 0 | 0 1 3 5 7 9 |
| 4 10 1 2 3 4 0 0 | 1 2 3 4 10 |
| 4 2 1 2 2 3 0 0 | 1 2 2 2 3 |
| 0 5 (空行或無後續數字) 0 0 | 5 |
MAXN = 101 (原 100 + 插入 1)，建議略大如 1050 0 也輸出left < right + right = mid / left = mid+1 是標準 Lower Bound 寫法有序陣列插入 = 查找位置 + 逆向移動 + 插入。小資料量用線性查找，大資料量用二分查找。掌握 Lower Bound 二分查找模板，可廣泛應用於 std::lower_bound、bisect_left 等標準庫函式的理解與手寫實作。
