LeetCode 35. 搜索插入位置：二分查找下界 C 語言標準解法

LeetCode 35. 搜索插入位置：二分查找下界 C 語言標準解法

給定有序無重複數組 `nums` 和目標值 `target`，返回目標索引（若存在）或應插入位置（保持有序）。本文提供**標準庫 `lower_bound` 語義**的二分查找實現：`while (l < r) mid = l + (r-l)/2; if (nums[mid] < target) l = mid+1; else r = mid;` 返回 `l`。

題目大意

• 輸入：升序數組 `nums` (長度 n)，目標 `target`。
• 輸出：`target` 索引（若存在），否則插入後保持有序的位置索引。
• 示例：`[1,3,5,6]`, 5→2；2→1；7→4；0→0。

核心邏輯：尋找第一個 ≥ target 的位置

這正是 C++ `lower_bound`、Java `Arrays.binarySearch` 返回插入點的語義。循環不變量：`[0, l)` 全 < target，`[r, n)` 全 ≥ target，收斂時 `l == r` 即為答案。

C 語言實現（標準二分）

int searchInsert(int* nums, int numsSize, int target) {
    int l = 0, r = numsSize; // 搜索區間 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2; // 防溢出
        if (nums[mid] < target) {
            l = mid + 1; // 目標在右半開區間
        } else {
            r = mid;     // 目標在左半閉區間（含 mid）
        }
    }
    return l; // l == r，即第一個 >= target 的位置
}

關鍵點解析

• 區間定義 `[l, r)` 左閉右開**：初始 `r = n` 允許插入到末尾（返回 n）。
• 分支邏輯：`< target` 走右，`>= target` 走左，**精準鎖定下界**。
• 無需特判存在性**：若存在，`l` 停在第一個等於 target 的位置（因無重複，即唯一位置）。
• 防溢出中點**：`l + (r-l)/2` 而非 `(l+r)/2`。

線性掃描版（教學/極小 n）

int searchInsert_linear(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= target) return i;
    }
    return numsSize;
}

O(n) 時間，代碼極簡，面試可作兜底並說明「若數組極小或有序性不可靠，線性更穩」。

複雜度對比

測試用例

nums=[1,3,5,6], target=5 → 2
nums=[1,3,5,6], target=2 → 1
nums=[1,3,5,6], target=7 → 4
nums=[1,3,5,6], target=0 → 0
nums=[], target=5 → 0
nums=[2], target=1 → 0
nums=[2], target=3 → 1

擴展：有重複元素數組

若數組允許重複，上述代碼返回**第一個 ≥ target 的位置**（即 `lower_bound`）。若需「最後一個 ≤ target」（`upper_bound - 1`），修改分支：`if (nums[mid] <= target) l = mid+1; else r = mid;` 返回 `l-1`。

總結

搜索插入位置本質是**二分查找下界**。掌握 `[l, r)` 區間不變量、`< target` 走右、`>= target` 走左、返回 `l` 的標準模板，可直接應用於「第一個錯誤版本 (LeetCode 278)」、「x 的平方根 (LeetCode 69)」、「在排序數組中查找元素第一/最後位置 (LeetCode 34)」等經典二分題。面試必會默寫模板，理解不變量是核心。