LeetCode 35 Search Insert Position：二分查找確定插入位置

題目大意

給定已排序陣列 nums（無重複元素）與目標值 target。若 target 存在，回傳其索引；否則回傳按順序插入時的索引（即第一個大於 target 的元素位置，或陣列末尾）。

範例：[1,3,5,6], target=5 → 2; target=2 → 1; target=7 → 4; target=0 → 0。

解法：標準二分查找變體

維護 low=0, high=n-1。迴圈條件 low <= high。計算 mid = (low+high)/2：

• nums[mid] < target：目標在右側，low = mid + 1。
• nums[mid] > target：目標在左側，high = mid - 1。
• nums[mid] == target：找到，回傳 mid。

迴圈結束時 low > high，此時 low 即為插入位置（第一個大於 target 的元素索引，或 n）。

C++ 完整實現

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2; // 避免溢位
            if (nums[mid] < target)
                low = mid + 1;
            else if (nums[mid] > target)
                high = mid - 1;
            else
                return mid;
        }
        return low;
    }
};

關鍵點解析

• mid = low + (high - low) / 2 防止 low+high 溢位（雖然此題 n 小不會溢位，但為良好習慣）。
• 迴圈不變量：目標插入位置恆在 [low, high+1] 區間內。
• 結束時 low == high + 1，區間縮減為單點 low，即答案。

複雜度

• 時間：O(log n)。
• 空間：O(1)。

延伸：C++ 標準庫 lower_bound

return lower_bound(nums.begin(), nums.end(), target) - nums.begin();

lower_bound 回傳第一個 >= target 的迭代器，完全符合題目需求。