题目链接 · 灵神原题解（署名来源）

题意概括

返回 $\mathit{\text{nums}}$ 中的第一个（最左边的）大于或等于 $\mathit{\text{target}}$ 的数的下标。如果所有数都小于 $\mathit{\text{target}}$，返回 $\mathit{\text{nums}}$ 的长度。

视频讲解

请看【基础算法精讲 04】。制作不易，欢迎点赞~

下面的代码包含闭区间、左闭右开区间和开区间三种写法。

选择自己喜欢的一种写法即可。

答疑

问：为什么不在二分的过程中，找到 $\mathit{\text{target}}$ 就立刻返回？

答：这种写法适用范围很窄。在有多个等于 $\mathit{\text{target}}$ 的数的情况下，如果在二分的过程中立刻返回，我们得到的可能不是第一个等于 $\mathit{\text{target}}$ 的数的下标。为什么返回第一个等于 $\mathit{\text{target}}$ 的数的下标更好呢？因为这可以解决更复杂的题目，比如给你一个有序数组 $[1,1,3,3,3,3,5]$，让你计算有多少个数小于 $3$。我们可以二分查找第一个等于 $3$ 的数的下标 $2$，那么下标小于 $2$ 的数就是元素值小于 $3$ 的数，这有 $2$ 个。对比可以发现，如果在二分中途就立刻返回，我们不一定找到的是第一个等于 $3$ 的数的下标，所以不一定能算出正确答案 $2$。

问：为什么代码没有特判所有数都小于 $\mathit{\text{target}}$ 的情况？

答：如果所有数都小于 $\mathit{\text{target}}$，那么循环中更新的只有 $\mathit{\text{left}}$，无论下面哪种二分写法，最后都一定会返回数组长度，所以无需特判这种情况。

问：如果所有数都大于 $\mathit{\text{target}}$ 呢？

答：代码会返回 $0$。

问：是否需要特判 $\mathit{\text{nums}}[\mathit{\text{mid}}]=\mathit{\text{target}}$ 的情况？

答：可以，但没必要。

Python 解法1

# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

# 闭区间写法
def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left

# 左闭右开区间写法
def lower_bound2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)  # 左闭右开区间 [left, right)
    while left < right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right)
        else:
            right = mid  # 范围缩小到 [left, mid)
    return left  # 或者 right

# 开区间写法
def lower_bound3(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)  # 开区间 (left, right)
    while left + 1 < right:  # 区间不为空
        mid = (left + right) // 2
        # 循环不变量：
        # nums[left] < target
        # nums[right] >= target
        if nums[mid] < target:
            left = mid  # 范围缩小到 (mid, right)
        else:
            right = mid  # 范围缩小到 (left, mid)
    return right

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return lower_bound(nums, target)  # 选择其中一种写法即可

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    // lower_bound 返回最小的满足 nums[i] >= target 的 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

    // 闭区间写法
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            } else {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            }
        }
        return left;
    }

    // 左闭右开区间写法
    int lower_bound2(vector<int>& nums, int target) {
        int left = 0, right = nums.size(); // 左闭右开区间 [left, right)
        while (left < right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1; // 范围缩小到 [mid+1, right)
            } else {
                right = mid; // 范围缩小到 [left, mid)
            }
        }
        return left;
    }

    // 开区间写法
    int lower_bound3(vector<int>& nums, int target) {
        int left = -1, right = nums.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid; // 范围缩小到 (mid, right)
            } else {
                right = mid; // 范围缩小到 (left, mid)
            }
        }
        return right;
    }

public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums, target); // 选择其中一种写法即可
    }
};

库函数写法

Python 解法3

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect_left(nums, target)

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return ranges::lower_bound(nums, target) - nums.begin();
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(\log n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$，仅用到若干额外变量。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府