35. 搜索插入位置
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例
示例 1：
输入：nums = [1,3,5,6], target = 5
输出：2
示例 2：
输入：nums = [1,3,5,6], target = 2
输出：1
示例 3：
输入：nums = [1,3,5,6], target = 7
输出：4
解题思路
第一步：理解问题本质
这是一个二分查找的变体问题。需要找到：
- 如果 target 存在，返回其索引
- 如果 target 不存在，返回它应该被插入的位置（第一个大于 target 的位置）
第二步：暴力解法
思路：线性扫描数组，找到 target 或第一个大于 target 的元素。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 第一个 >= target 的位置，就是 target 该待的地方
for i in range(len(nums)):
if nums[i] >= target:
return i
# 全都比 target 小，插到末尾
return len(nums)
缺点：时间复杂度 O(n)，不满足 O(log n) 的要求。
第三步：最优解法 —— 二分查找
核心洞察：
- 如果找到 target，返回其索引
- 如果没找到，循环结束时
left指向的位置就是插入位置
为什么返回 left？
- 循环不变式：
nums[0..left-1] < target，nums[right..n-1] >= target - 当循环结束时，
left == right，区间收缩到同一个点 - 这个点就是第一个大于等于 target 的位置
算法步骤：
- 初始化
left = 0, right = n - 循环条件
left < right：nums[mid] >= target：target 在左半区（或已找到），right = midnums[mid] < target：target 在右半区，left = mid + 1
- 循环结束
left == right，返回 left
完整代码实现
算法可视化 · 逐帧回放这道题的代码13 帧 · 录制输入 [1,3,5,6], 5
from typing import List
class Solution:
"""
搜索插入位置 - 二分查找
核心思想：
在有序数组中找 target 的插入位置，使得插入后数组仍然有序。
这等价于找第一个大于等于 target 的元素位置。
二分查找的变体：
- 如果找到 target，返回其索引
- 如果没找到，left 指向的位置就是应该插入的位置
（因为循环结束时，left 是第一个 >= target 的位置）
为什么返回 left？
循环不变式：nums[0..left-1] < target，nums[right..n-1] >= target
当循环结束时，left == right，两者都停在第一个 >= target 的位置
时间复杂度：O(log n)
空间复杂度：O(1)
"""
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n # 右边界设为 n，左闭右开区间
while left < right: # 不使用 <=：左闭右开写法更统一，循环结束时 left == right 即为答案
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid # 收缩右边界到 mid
else:
left = mid + 1 # target 在右半区
return left
示例推演
以 nums = [1,3,5,6], target = 2 为例：
| 步骤 | left | right | mid | nums[mid] | 操作 |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 5 | 5 >= 2，right = 2 |
| 2 | 0 | 2 | 1 | 3 | 3 >= 2，right = 1 |
| 3 | 0 | 1 | 0 | 1 | 1 < 2，left = 1 |
| 4 | 1 | 1 | - | - | left == right，结束 |
返回 left = 1
解释：2 应该插入到索引 1 的位置，结果数组为 [1,2,3,5,6]
再以 nums = [1,3,5,6], target = 7 为例：
| 步骤 | left | right | mid | nums[mid] | 操作 |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 5 | 5 < 7，left = 3 |
| 2 | 3 | 4 | 3 | 6 | 6 < 7，left = 4 |
| 3 | 4 | 4 | - | - | left == right，结束 |
返回 left = 4
解释：7 应该插入到数组末尾，索引为 4
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力 | O(n) | O(1) | 线性查找 |
| 二分查找（最优） | O(log n) | O(1) | 满足题目要求 |
易错点总结
1. 右边界初始化与循环写法要自洽
本题用左闭右开写法：right = n，循环条件 left < right，收缩时 right = mid。
循环收在 left == right 处，这个下标就是第一个 >= target 的位置：
# 左闭右开：left 是候选答案，right 是「取不到」的上界
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left # 此时 left == right，就是插入位置
如果改成闭区间 right = n - 1、while left <= right，循环结束时 left = right + 1，
返回的仍然是 left，但中间所有边界都要跟着改。两种写法不能混用，
混用才会出现少算一格或多算一格。
2. 注意边界条件
target比所有元素都小：返回 0target比所有元素都大：返回len(nums)target等于某个元素：返回该元素的索引
3. mid 的计算
# 等价于 (left + right) // 2，但避免两数先相加时溢出
mid = left + (right - left) // 2 # 防止溢出
扩展思考
1. lower_bound 和 upper_bound
- lower_bound：第一个 >= target 的位置（本题）
- upper_bound：第一个 > target 的位置
2. 如果数组中有重复元素？
本题返回任意一个 target 的位置都可以，如果要返回最左/最右的位置，需要修改二分查找逻辑。