LeetCode Search Insert Position：二分查找插入位置即 lower_bound

題目回顧

有序無重複數組，找 target 索引；不存在則返回應插入的位置。
例：[1,3,5,6], target=2 → 1；target=7 → 4；target=0 → 0

核心洞察：即 lower_bound

返回第一個 ≥ target 的位置。標準二分模板：

int searchInsert(vector& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

Python 代碼

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

邊界情況自動覆蓋

• target 比所有元素大 → left = n
• target 比所有元素小 → left = 0
• target 存在 → 返回第一個等於 target 的位置（無重複即唯一位置）

測試用例

assert Solution().searchInsert([1,3,5,6], 5) == 2
assert Solution().searchInsert([1,3,5,6], 2) == 1
assert Solution().searchInsert([1,3,5,6], 7) == 4
assert Solution().searchInsert([1,3,5,6], 0) == 0