LeetCode 35. 搜索插入位置

2025-07-24 HGNULB 约 5 分钟

文章信息 11 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 5-10 字节跳动微软快手腾讯 LeetCode 热题 100 面试经典 150 题

题目描述

✅ 35. 搜索插入位置

题意分析

给一个升序排列且互不相同的整数数组和一个目标值，如果目标值存在就返回它的下标，不存在则返回它按顺序插入后应当占据的下标。

题目问的是两件事，但答案可以合并成一件。无论目标值在不在数组里，要返回的都是「插入后它所处的位置」——存在时插到它自己所在的位置，不存在时插到第一个比它大的元素之前。因此整道题可以重述为：求满足 nums[i] >= target 的最小下标 $i$。这一步合并很关键，否则会写出「先查找，找不到再算插入点」的两段式代码。

约束透露的信号非常直白：数组严格升序，且明确要求时间复杂度为 $O(\log n)$。有序 + 对数时间，等于点名了必须在有序性上做折半决策，顺序扫描虽然能过样例但违反约束。

无重复这个条件降低了难度：如果允许重复，「返回下标」就有歧义，而这里目标值最多出现一次，所以「第一个大于等于」与「等于」在存在时必然指向同一个位置。

边界情况：目标值比所有元素都小时答案是 0；比所有元素都大时答案是数组长度 $n$，注意这个下标已经越界，是一个合法但不可访问的位置；数组长度为 1 时只有两种结果 0 或 1；题目保证 $n \ge 1$，但实现上仍应确认空数组不会崩。

解法：二分查找第一个大于等于目标的位置

核心思路

无论 target 是否存在，答案都是“第一个大于等于 target 的下标”；若所有元素都更小，答案就是数组长度。这正是标准的 lower_bound。

在左闭右开区间 [left, right) 上二分，并维护：

[0, left) 中的元素都小于 target，不可能是答案；

[right, n) 中的元素都大于等于 target，都是候选位置。

若 nums[mid] < target，mid 及其左侧都可排除，令 left = mid + 1；否则 mid 仍可能是第一个合法位置，令 right = mid。每轮区间严格缩小，结束时 left == right，它就是左右两类的分界点。

右边界初始设为 n 很关键：这样“插到数组末尾”无需额外分支，也能作为合法答案保留下来。

解题步骤

初始化 left = 0、right = nums.length，搜索区间为 [left, right)。

当 left < right 时计算 mid = left + (right - left) / 2。

若 nums[mid] < target，令 left = mid + 1。

否则令 right = mid，继续向左寻找更早的合法位置。

循环结束后返回 left。

例如 nums = [1, 3, 5, 6]、target = 2：先检查 5，收缩到左半边；再检查 3，继续收缩左边界，最终停在下标 1，正好应插在 1 和 3 之间。

代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

复杂度分析

时间复杂度：$O(\log n)$，每轮将候选区间缩小约一半。

空间复杂度：$O(1)$，只使用常数个变量。

关键点总结

先把“找到目标或插入位置”统一成“找第一个大于等于目标的位置”。

左闭右开写法让 n 自然成为合法答案，不需要单独处理插到末尾。

更新 right = mid 是因为 mid 仍可能是答案；更新 left = mid + 1 是因为 mid 已确定不合法。

二分代码应先写清区间含义和不变量，再决定循环条件与边界更新。

易错点总结

把 right 初始化为 n - 1，却继续使用左闭右开模板，会漏掉末尾插入位置。

当 nums[mid] >= target 时写成 right = mid - 1，会错误排除可能的答案。

当 nums[mid] < target 时只令 left = mid，在区间长度为 1 或 2 时可能死循环。

循环结束后访问 nums[left] 再判断会在 left == n 时越界；直接返回分界点即可。

只在相等时返回、未找到后再猜插入点，会增加边界分支且更容易出现偏一错误。

相似题目

题目	难度	考察点
704. 二分查找	简单	只判存在性，命中即返回，不需要继续向左收缩
34. 在排序数组中查找元素的第一个和最后一个位置	中等	元素可重复，要把同一模板正反各跑一次求左右边界
LCR 068. 搜索插入位置	简单	与本题同题面，可用来对照检验模板是否真的背熟
278. 第一个错误的版本	简单	判定式换成 API 调用，考点转为如何减少调用次数
剑指 Offer 53 - I. 在排序数组中查找数字 I	简单	求出现次数，用两次边界查找相减而非逐个统计
剑指 Offer 53 - II. 0～n-1中缺失的数字	简单	判定式变成 `nums[i] != i`，二分的对象是下标与值的错位
540. 有序数组中的单一元素	中等	数组本身无单调性，靠成对结构的奇偶下标构造单调判定
LCR 070. 有序数组中的单一元素	中等	同上，但常被要求给出不依赖奇偶特判的写法
367. 有效的完全平方数	简单	没有数组，在值域上二分，注意乘积溢出
875. 爱吃香蕉的珂珂	中等	二分答案，判定式是一次 $O(n)$ 的可行性模拟
33. 搜索旋转排序数组	中等	整体无序，需先判断哪半有序再决定收缩方向
162. 寻找峰值	中等	无目标值，靠与相邻元素的大小关系决定往哪半走
面试题 10.05. 稀疏数组搜索	简单	存在空串，`mid` 需要先线性挪到最近的非空位置