题目

解法：二分查找

思路

核心思想是二分查找的左边界搜索变体，目标是找到第一个大于等于目标值的元素位置。

该方法的正确性基于循环不变量：在每次循环开始时，区间 [l, r] 始终包含目标值的插入位置。当 nums[mid] < target 时，说明插入位置必在 mid 右侧，故将 l 移动到 mid + 1；否则插入位置在 mid 或左侧，故将 r 收缩至 mid。循环结束时 l == r，指向的就是第一个大于等于 target 的元素位置。最后检查 nums[l] < target 的情况，仅当 target 大于数组所有元素时需要插入到末尾，此时 l 自增返回数组长度。

• Step 1: 初始化左右指针 l = 0, r = nums.size() - 1
• Step 2: 当 l < r 时循环，计算中点 mid = l + (r - l) / 2
• Step 3: 若 nums[mid] < target，则 l = mid + 1，否则 r = mid
• Step 4: 循环结束后，若 nums[l] < target，则 l++
• Step 5: 返回 l 作为插入位置

复杂度

• 时间复杂度: $O(\log n)$
• 空间复杂度: $O(1)$

代码

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