LeetCode 35 搜索插入位置：二分查找標準解法與邊界處理技巧

題目大意

給定一個升序無重複數組 nums 和目標值 target，若目標值存在返回其下標；否則返回其應插入的位置以保持數組有序。例如：
[1,3,5,6], 5 → 2；[1,3,5,6], 2 → 1；[1,3,5,6], 7 → 4；[1,3,5,6], 0 → 0。

二分查找核心邏輯

維護左閉右閉區間 [left, right]，每輪取中間索引 mid = left + (right - left) / 2：

• 若 nums[mid] == target，直接返回 mid
• 若 nums[mid] < target，目標在右半區，left = mid + 1
• 若 nums[mid] > target，目標在左半區，right = mid - 1

循環結束時 left > right，此時 left 即為插入位置。因為：

• 所有 < target 的元素在 left 左側
• 所有 > target 的元素在 right 右側
• left == right + 1，空位正好在 left

標準 C++ 實現

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left = 0, right = (int)nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left; // 未找到時 left 即插入位置
    }
};

關鍵細節與變體

1. 避免溢出的中間值計算

使用 mid = left + (right - left) / 2 而非 (left + right) / 2，防止 left + right 超過 INT_MAX。

2. 區間定義的統一性

本解法採用 左閉右閉 [left, right]，循環條件 left <= right，更新邊界時 +1/-1。若改用左閉右開 [left, right)，則循環條件為 left < right，更新 left = mid + 1 / right = mid，返回 left 同理。

3. 原文代碼的邏輯缺陷

原文採用 if (A[m] > target) return m; else return m + 1; 判斷插入位置，但循環結束時 m 為最後一次計算的中間值，未必等於 left，可能導致邊界錯誤。標準寫法直接返回 left 更穩健。

複雜度分析

• 時間複雜度：O(log n)，每輪搜索範圍減半
• 空間複雜度：O(1)，僅使用常數額外變量

相關題目延伸

• LeetCode 34 在排序數組中查找元素的第一個和最後一個位置
• LeetCode 74 搜索二維矩陣
• LeetCode 34 變體：查找首尾位置

總結

搜索插入位置是二分查找的經典應用，關鍵在於理解循環終止時 left 的語義：它始終指向第一個 ≥ target 的位置，正是插入點。掌握左閉右閉/左閉右開兩種區間寫法並能相互轉換，是二分查找進階的基礎。