35. 搜索插入位置

难度：🟢 Easy | 标签：二分查找 | 状态：⬜ LeetCode 链接

思路

找第一个 >= target 的下标 = 答案。 左闭右开区间二分（[l, r)），找下界模板。

代码

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

复杂度

• 时间 O(log n)，空间 O(1)

易错 / 回顾

• r = nums.size()，允许 l 走到末尾（插入到末尾）
• nums[m] >= target 收右；< 收左 + 1
• mid = l + (r - l) / 2 防溢出