LeetCode 35. 搜索插入位置

◎

本节目标

将精确查找推广为第一个不小于目标的插入位置。

这道题把二分查找解题框架的边界抽象直接作为答案：返回第一个不小于 target 的位置。

查看原题

题意与约束

给定严格递增数组，若目标存在则返回其下标；否则返回按顺序插入后应处的下标。

朴素思路与瓶颈

从左到右寻找第一个不小于 target 的元素，最坏会扫描整个数组。由于“不小于目标”在递增数组中呈现一段假、一段真的单调结构，可以直接二分真假分界。

第一个不小于目标的位置

在半开区间 [left, right) 中维护候选插入位置：

• nums[mid] >= target 时，mid 及其左侧仍可能是第一个合法位置，收缩 right = mid；
• nums[mid] < target 时，mid 一定不能插入目标，收缩 left = mid + 1。

因此无论目标是否存在，最终 left 都在 [0, n] 内：它可以是首位、中间、末尾后的 n，也可以正好是已有目标的位置。

代码实现

源码只维护一个边界，不需要在循环外单独处理“找到”与“未找到”。

C++

C++17

#include <vector>
using namespace std;

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

Python

Python 3

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

复杂度分析

• 时间复杂度：O(log n)。
• 空间复杂度：O(1)。

易错点

• 右端初始化为 n，因为插入位置允许在最后一个元素之后。
• nums[mid] == target 时仍向左收缩，才能得到第一个位置。
• 空数组收敛到 0，正是唯一的合法插入位置。

模式迁移

把“元素值不小于目标”换成任意单调条件，就得到边界二分；它是查首尾位置和二分答案的共同基础。