LeetCode Search Insert Position：二分查找變體求插入位置

問題描述

給定升序無重複數組 nums 和目標值 target。若存在返索引，否則返回「按順序插入」的位置（即第一個 ≥ target 的元素索引，或數組長度）。

二分查找模板

維持不變量：[left, right] 為答案可能區間。循環條件 left <= right。

int searchInsert(vector& nums, int target) {
    int left = 0, right = 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 = right+1，即插入位置
}

關鍵點

• 返回 left 而非 mid：循環結束時 left 指向第一個大於 target 的位置
• 無重複元素保證，若有重複需用 lower_bound 邏輯
• 時間 O(log n)，空間 O(1)

示例

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