企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文是「算法通关手册」LeetCode 题解库 中对0035. 搜索插入位置的完整解析。该题是二分查找在「查找插入位置」场景下的经典入门题目：给定一个已升序排列的无重复元素数组与目标值，要求在 $O(\log n)$ 时间内返回目标值的下标；若目标值不存在，则返回其应被按顺序插入的位置。通过本文，你将掌握左闭右闭区间二分查找的直接法实现、插入位置边界的推导逻辑，以及如何与仓库中的二分查找基础理论章节相互印证，为后续解决「寻找边界值」「旋转排序数组」等进阶二分题目打下基础。

1. 题目信息与题意梳理

• 题目编号：0035
• 标签：数组、二分查找
• 难度：简单
• 题目链接：搜索插入位置（力扣原题，题号 0035）

1.1 题目大意

给定一个排好序的数组nums，以及一个目标值target。要求在数组中找到目标值，并返回其下标；如果找不到，则返回目标值按顺序插入数组的位置。

1.2 题目说明与约束

注意约束中「无重复元素 + 升序排列」这一前提。它保证了二分查找在缩小区间时不会因为重复值而出现歧义，是本题可以使用标准二分直接求解的关键前提。若数组存在重复元素，插入位置的判定就需要退化为「找第一个大于等于target的位置」这类边界问题，对应仓库中 01_14 数组二分查找（二） 所讨论的「排除法」场景。

1.3 示例

示例 1：

输入：nums = [1,3,5,6], target = 5 输出：2

nums[2] == 5，目标值存在，直接返回下标2。

若将target改为2或7，则目标不存在：2应插入下标1与3之间（即返回1），7应插入数组末尾（即返回4，等于len(nums)）。

2. 解题思路：为什么选择二分查找

题目要求的目标是一个「升序数组中的查找 / 插入点定位」问题，数组天然有序且无重复，这正符合二分查找的适用条件。在仓库的二分查找基础章节 01_13 数组二分查找（一） 中明确指出：二分查找算法又称折半查找、对数查找，核心思想是每次将查找区间缩小一半，从而快速锁定目标位置；其时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$，而线性遍历的复杂度为 $O(n)$。

本题与仓库中 0704. 二分查找 的不同点在于：当目标不存在时，704 题要求返回-1，而本题要求返回按顺序插入的位置。这个差异恰恰是二分查找循环终止后的边界推导关键，也是本题作为「查找插入位置」应用场景的代表意义所在。

思路 1：二分查找（直接法）

采用仓库二分查找章节推荐的左闭右闭区间写法，即查找区间为 $[left, right]$，初始化left = 0、right = len(nums) - 1。整体流程如下：

1. 取两个节点中心位置mid = left + (right - left) // 2（该写法通过减法规避了left + right潜在的整型溢出风险，虽然 Python 不会溢出，但其他语言需要）；
2. 比较中心位置值nums[mid]与目标值target的大小：
   • 如果target == nums[mid]，则当前中心位置即为目标下标，直接返回mid；
   • 如果target > nums[mid]，则将左节点设置为mid + 1，继续在右区间 $[mid + 1, right]$ 搜索；
   • 如果target < nums[mid]，则将右节点设置为mid - 1，继续在左区间 $[left, mid - 1]$ 搜索；
3. 直到查找到目标值返回下标，或者等到left > right时停止查找——此时**left所在位置就是待插入数组的位置**。

为什么循环终止时返回left就是插入位置？可以从区间收缩过程推导：每次收缩都保证「left左侧的元素都小于target」这一不变量成立。当left > right时，说明left已经越过最后一个小于target的元素，恰好停留在第一个大于等于target的元素处；若target大于数组所有元素，则left最终等于len(nums)，即插入数组末尾。

思路 1：二分查找代码

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

思路 1：复杂度分析

• 时间复杂度：$O(\log n)$。每次循环都将查找区间缩小一半，二分查找的时间复杂度为 $O(\log n)$。
• 空间复杂度：$O(1)$。只用到了常数个变量存放若干中间结果。

3. 边界情况推演：插入位置为何是left

为帮助读者彻底理解「找不到时返回left」的结论，下面用两个典型场景手工推演一遍循环过程。

场景一：target小于数组首元素

nums = [1,3,5,6]，target = 0：

1. left = 0, right = 3，mid = 1，nums[1] = 3 > 0→right = 0；
2. left = 0, right = 0，mid = 0，nums[0] = 1 > 0→right = -1；
3. 循环终止（left = 0 > right = -1），返回left = 0。0应插在数组最前面，下标0，正确。

场景二：target大于数组所有元素

nums = [1,3,5,6]，target = 7：

1. left = 0, right = 3，mid = 1，nums[1] = 3 < 7→left = 2；
2. left = 2, right = 3，mid = 2，nums[2] = 5 < 7→left = 3；
3. left = 3, right = 3，mid = 3，nums[3] = 6 < 7→left = 4；
4. 循环终止（left = 4 > right = 3），返回left = 4，等于数组长度，即插入数组末尾，正确。

可见，left的最终值天然覆盖了「最前插入」「中间插入」「末尾插入」三种情况，无需在循环外再做额外判断，这正是直接法配合左闭右闭区间的优雅之处。

4. 仓库源码级补充：二分查找的实现细节

本题代码是仓库 01_13 数组二分查找（一） 中「直接法」思路的直接应用。该基础章节总结了二分查找的几个关键实现要点，可用来对照验证本题代码：

• 区间定义：统一使用左闭右闭区间[left, right]，初始化right = len(nums) - 1；
• 中间下标计算：推荐mid = left + (right - left) // 2的防溢出写法；
• 区间收缩：目标在右半区间时left = mid + 1，在左半区间时right = mid - 1；
• 终止条件：left > right时查找区间为空。

而 01_14 数组二分查找（二） 进一步指出，二分查找有「直接法」与「排除法」两种思路：直接法在循环体内命中即返回、循环条件为left <= right，适合元素性质简单、==/>/<分支清晰的题目，本题正属于此类；排除法则在每轮排除一定不含目标的区间、循环条件为left < right、结束时还需额外判断nums[left]，更适合「数组中可能不存在的元素」「找边界」等复杂问题。

从源码结构看，仓库的 Python 代码目录 codes/python 中并未收录 LeetCode 单题提交文件，LeetCode 题目的标准实现统一以 Markdown 形式收录在 docs/solutions 各题号区间目录下，因此本题的标准答案即上文所给代码，可直接复制到 LeetCode 对应题目的答题区运行验证。

5. 变体思路：Python 标准库bisect与排除法

本题本质上是在寻找「第一个大于等于target的下标」，该语义与 Python 标准库bisect模块高度一致：

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

bisect_left返回「将target插入nums后仍保持有序的最左侧位置」，对无重复升序数组而言，其行为与本题要求完全等价。了解这一对应关系，有助于在工程开发中快速复用标准库，但在算法面试中仍建议手写二分以体现对边界细节的掌控。

若改用「排除法」思路实现，代码形态如下（循环结束后left == right，该位置即为插入点）：

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

这里while left < right搭配right = mid（而非right = mid - 1），属于 01_14 数组二分查找（二） 中「排除法」的配对写法，读者可以对照该章节进一步体会两种思路的差异与适用边界。

6. 延伸学习：二分查找进阶题目

本题被收录在仓库「二分查找题目列表」中（见 00_06 分类题目列表 的「二分查找题目」一节）。完成本题后，建议按以下顺序循序渐进地练习二分查找的各类变体：

其中 0034 题 与本题关系最紧密：它在有重复元素的升序数组上同时求「第一个」与「最后一个」位置，正是把本题「找第一个大于等于target的位置」思想推广到左右边界的结果，可作为巩固排除法的最佳后续练习。

7. 总结

• 核心结论：升序无重复数组上，查找目标下标或插入位置可以在 $O(\log n)$ 内完成，标准写法是左闭右闭区间 + 直接法二分。
• 关键细节：mid使用left + (right - left) // 2防溢出；循环条件left <= right；命中即返回；循环终止后返回left即为插入位置（覆盖首、中、尾三种插入场景）。
• 复杂度：时间 $O(\log n)$，空间 $O(1)$。
• 进阶路径：从本题出发，可顺次掌握「排除法」、边界查找（0034）与旋转数组二分（0033），二分查找相关理论可随时回看 01_13 二分查找（一） 与 01_14 二分查找（二） 两个基础章节。

• 教程
• 文档
• 知识库