LeetCode 35. 搜索插入位置

约 4 分钟
文章信息 11 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 LeetCode 热题 100 面试经典 150 题 腾讯 字节 微软 快手
标签
数组 二分查找

题目描述

✅ 35. 搜索插入位置

image-20260928234129427

image-20260928234129429

题意分析

给定无重复元素的升序数组和目标值：目标存在时返回它的下标，否则返回把它插入后仍能保持升序的位置。返回的是下标，不需要实际插入或修改数组。

插入位置可以是开头，也可以是所有元素之后的下标 n。两种返回要求可以统一成一个边界：找到第一个大于等于目标的元素位置；如果所有元素都更小，就返回 n。题目要求对数时间，适合直接二分这个边界。

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

核心思路

[!blue]

升序使所有小于目标的元素构成左边一段，所有大于等于目标的元素构成右边一段。目标边界就在这两段之间。维护左闭右开的待判断元素区间 [left, right)，同时保证下标小于 left 的元素都小于目标，下标大于等于 right 的实际元素都大于等于目标。

初始 left = 0、right = n，两侧都还没有实际元素被排除。right = n 虽然不是可访问的数组下标，却是合法的最终插入位置；只要循环仍有 left < right，计算出的中点就一定小于 right，不会访问到 nums[n]。

如果 nums[mid] < target，中点及其左边的候选元素都太小，可以全部排除，令 left = mid + 1。否则中点已经符合右侧条件，最早边界不会在它右边，令 right = mid；中点保留为可能的边界，不需要再当作待判断元素重复检查。

每次更新都保持两侧性质，同时严格缩小未判断区间。最终 left == right 时，所有左侧元素都小于目标，所有右侧元素都大于等于目标，交界位置就是答案。目标存在时这个位置正好命中目标；不存在时，把目标放在这里也不会破坏顺序。

解题步骤

  1. 令 left = 0、right = nums.length。
  2. 当 left < right 时，计算中点 mid = left + (right - left) / 2。
  3. 若中点值小于目标，令 left = mid + 1；否则令 right = mid。
  4. 两端重合后直接返回 left，不要再读取该位置的数组元素来判断是否存在。

代码实现

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)$，只保存两个边界和中点下标。

关键点总结

[!green]

  • 查找和插入统一为第一个不小于目标的边界，无需分开处理相等与未找到。
  • right 是右开边界，也能作为最终答案，初始取 n 才能覆盖插到末尾。
  • 中点太小时已经不可能是答案，左端跨过它；中点足够大时仍可能是边界，右端保留它。
  • 返回时只需要边界下标，末尾插入位置不允许被解引用。

易错点总结

[!yellow]

  • 初始化 right = n - 1 却沿用右开区间更新方式，会漏掉最后的插入边界。
  • 中点值大于等于目标时写成 right = mid - 1，会跳过仍可能正确的边界位置。
  • 中点值小于目标时只令 left = mid，范围可能不再缩小，形成死循环。
  • 结束后访问 nums[left]，会在答案为 n 时越界；直接返回下标即可。
  • 把返回值理解成前一个较小元素的下标，混淆了插入位置与左邻居位置。

相似题目

题目 难度 关联与区别
34. 在排序数组中查找元素的第一个和最后一个位置 中等 同样查找有序数组的边界，本题只找第一个不小于目标的位置，原题还需找到最后一次出现。
704. 二分查找 简单 原题只判断目标是否存在，本题不存在时也要返回唯一插入位置。
69. x 的平方根 简单 在有序或具有单调判定的区间进行边界二分；本题寻找第一个不小于目标的位置，该题以平方是否超过输入作为判定。
367. 有效的完全平方数 简单 在有序或具有单调判定的区间进行边界二分；本题寻找第一个不小于目标的位置，该题检查平方根边界是否精确命中。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/97619395
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！