LeetCode LCR 068. 搜索插入位置

2026-03-28 HGNULB 约 7 分钟

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

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 068. 搜索插入位置

题意分析

给一个升序且元素互不相同的数组和一个目标值：目标值存在就返回它的下标，不存在就返回「把它插进去仍保持升序」的那个下标。

两种情况其实是同一个问题。无论目标是否存在，要返回的都是第一个大于等于目标的位置：目标存在时，那个位置上的元素恰好等于目标，返回的就是它的下标；目标不存在时，那个位置正是它该被插入的地方。把两种情况合并成一个统一的语义，是这题唯一需要想清楚的事。

题目明确要求 $O(\log n)$，这直接锁死了做法——必须用二分。同时「数组升序」是二分成立的前提，「元素互不相同」则让答案唯一，不必考虑重复值时取左边还是右边。

边界上要注意：目标可能小于所有元素，答案是 0；目标可能大于所有元素，答案是 $n$，这个下标越出数组范围但完全合法，正是「追加到末尾」的意思；数组长度至少为 1。

解法：二分查找判定答案

核心思路

暴力做法是从左往右扫描，遇到第一个大于等于目标的元素就返回它的下标，扫完还没遇到就返回 $n$。逻辑完全正确，代价是 $O(n)$，与题目要求的 $O(\log n)$ 不符。

瓶颈在于线性扫描没有利用「数组有序」这个前提：一旦知道 nums[mid] >= target，那么 mid 右边的所有元素也都大于等于目标，它们不可能是「第一个」，整段可以一次性丢弃；反过来 nums[mid] < target 时，mid 及其左边全部出局。每次比较都能砍掉一半候选。

于是把问题定义成在 [0, n] 这个闭开区间上找边界。注意搜索范围的右端取 $n$ 而不是 $n - 1$：答案允许等于 $n$（目标比所有元素都大），如果右端只到 $n - 1$，这个合法答案就永远无法被返回。

维护的不变量是：答案始终落在 [left, right] 之内；left 左边的元素全部小于目标，right 及其右边的元素全部大于等于目标。每轮取中点 mid：若 nums[mid] >= target，说明 mid 本身就是一个「大于等于目标的位置」，答案不会在它右边，令 right = mid（保留 mid，因为它可能就是答案）；否则 mid 及左边全部小于目标，令 left = mid + 1。

循环条件是 left < right，区间长度降为 1 时退出，此时 left == right 就是那个唯一满足不变量的位置，也就是第一个大于等于目标的下标。因为每轮区间至少缩短一半且 left 严格右移或 right 严格左移，循环必定终止，不会死循环。

解题步骤

令 left = 0、right = nums.length。右端取 $n$ 是为了容纳「插入到末尾」这个合法答案，取 $n - 1$ 会让目标大于所有元素时返回错误的 $n-1$。

循环条件写 left < right。区间是左闭右开语义下的候选集合，两端相等时候选唯一，无需再比较。

中点用 (left + right) >>> 1 计算。无符号右移可以避免 left + right 在极大下标时溢出成负数；用 left + (right - left) / 2 是等价的写法。

比较 nums[mid] >= target 时收缩右端到 mid，不是 mid - 1。因为 mid 自己就满足「大于等于目标」的条件，它有资格成为答案，排除掉就可能丢解。

否则说明 nums[mid] < target，mid 永远不可能是答案，令 left = mid + 1 把它排除。这里必须是 mid + 1 而不是 mid，否则区间不再收缩，会死循环。

退出后 left 与 right 相等，直接返回 left。不需要在返回前再判断一次 nums[left] == target——统一语义已经保证两种情况都对。

以 nums = [1, 3, 5, 6]、target = 2 走一遍：初始 left = 0、right = 4。第一轮 mid = 2，nums[2] = 5 >= 2，答案不在右半边，right = 2，区间收缩为 [0, 2)。第二轮 mid = 1，nums[1] = 3 >= 2，right = 1，区间收缩为 [0, 1)。第三轮 mid = 0，nums[0] = 1 < 2，这个位置出局，left = 1。此时 left == right == 1，退出循环返回 1——正是 2 应当插入的位置（插入后数组变成 [1, 2, 3, 5, 6]）。若把 target 换成 7：第一轮 mid = 2，5 < 7，left = 3；第二轮 mid = 3，6 < 7，left = 4；此时 left == right == 4，返回 4，恰好是数组长度，表示追加到末尾。

代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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

复杂度分析

时间复杂度：$O(\log n)$，每轮循环把候选区间的长度至少减半，从 $n$ 缩到 1 需要 $\lceil \log_2 n \rceil$ 轮，每轮只做一次比较。

空间复杂度：$O(1)$，只用了三个下标变量，没有任何与输入规模相关的额外结构，也没有递归栈。

关键点总结

「找目标下标」与「找插入位置」被统一成「找第一个大于等于目标的位置」，两个分支合并成一个语义后，代码不需要任何特判。遇到多情形的题，先找能覆盖全部情形的统一定义，往往能消掉大半的边界处理。

搜索区间的右端要根据答案的取值范围来定，而不是照抄数组的最大下标。本题答案可以取到 $n$，右端就必须是 $n$。

收缩规则要与判定条件严格对应：满足条件的 mid 有资格当答案，必须保留（right = mid）；不满足的必须排除（left = mid + 1）。一保留一排除，既保证不丢解又保证区间严格缩短。

循环条件 left < right 配合「返回 left」是左边界二分的固定组合，退出时两者必然相等，不需要在循环外再做任何判断。

中点计算用无符号右移或 left + (right - left) / 2，是处理大下标时防溢出的标准写法，即使本题规模用不上也应形成肌肉记忆。

面试视角：写完后主动说明「这是 lower_bound 语义」，并顺带给出 upper_bound 只需把判定改成 nums[mid] > target，能一次性展示你掌握的是模板背后的边界规则而不是背下来的四行代码。

面试视角：常见追问是「如果数组允许重复元素，要返回目标第一次出现的位置怎么办」。答这份代码原封不动就是答案，因为 >= 会一直向左收缩到第一个等于目标的位置；若要最后一次出现，改用 > 求出上界再减一。

易错点总结

错误写法：right 初始化为 nums.length - 1。用例 nums = [1, 3, 5]、target = 7 → 搜索区间永远够不到下标 3，返回 2，正确答案是 3。

错误写法：满足条件时写 right = mid - 1。用例 nums = [1, 3, 5]、target = 3 → 下标 1 这个正确答案被直接排除，最终返回 2，正确答案是 1。

错误写法：不满足条件时写 left = mid。用例 nums = [1, 3]、target = 3 → mid 恒等于 0 且 left 永远停在 0，区间不再收缩，死循环。

错误写法：循环条件写成 left <= right 且仍在循环内返回 left。用例 nums = [1]、target = 1 → left 与 right 相等时仍进入循环，right = mid = 0 不再变化，死循环。

错误写法：判定条件写成 nums[mid] > target。用例 nums = [1, 3, 5]、target = 3 → 求到的是第一个严格大于 3 的位置，返回 2，正确答案是 1。

错误写法：中点写成 (left + right) / 2 且在下标可能极大的场景中使用。用例极大下标相加溢出 → mid 变成负数，访问数组时抛越界异常；本题规模虽不触发，但同一模板搬到二分答案题（上界可达 $10^9$）时立刻出错。

错误写法：返回前额外判断 if (nums[left] == target) return left; else return left + 1。用例 nums = [1, 3, 5]、target = 2 → nums[1] = 3 不等于 2 于是返回 2，正确答案是 1；统一语义下的 left 本身就已经是答案。

错误写法：先特判 target 大于末元素时返回 n、小于首元素时返回 0，再对中间做二分。用例 nums = [1]、target = 1 → 多余的特判分支容易把等号写漏，等于末元素时被误判成「大于」而返回 1，正确答案是 0；统一语义本就无需特判。

相似题目

题目	难度	考察点
35. 搜索插入位置	简单	与本题同题，是左边界二分最干净的样板
704. 二分查找	简单	只需判断存在性，可用闭区间写法对照两套模板的退出条件差异
34. 在排序数组中查找元素的第一个和最后一个位置	中等	数组含重复元素，需要同时求下界与上界并处理目标不存在的情形
278. 第一个错误的版本	简单	判定条件由接口给出而非数组比较，考察抽象出「第一个为真」的边界
540. 有序数组中的单一元素	中等	判定依据变成下标的配对奇偶性，二分的对象不再是元素值本身
162. 寻找峰值	中等	数组无序，靠相邻元素的大小关系推断答案侧，收缩规则需重新论证
367. 有效的完全平方数	简单	二分的是答案值域而不是数组下标，右端上界要自己确定