搜索插入位置 图解题解
找插入位置和找目标下标本质一样——二分找「第一个不小于 target 的位置」，存不存在都能给出答案。
在已经按号码排好的候场队列里插一张新票，找它该站的位置——不用从头一张张比，直接翻到中间：中间号码大于等于新票就往左缩，小于就往右缩，且 r 初始设成「队尾再往后一格」，因为新票可能要排到最末尾。区间收拢到空时，l 指的就是第一个「不小于目标」的位置，即插入点。
这道题到底在问什么
- nums
- [1, 3, 5, 6]
- target
- 2
- 输出
- 1
先想最直接的笨办法
挨个比，碰到第一个大于等于 target 的位置就是答案。能对，但要 O(n)。数组明明是升序的，这个条件白白浪费了。（动画第 3 步）
最优解：一步一步想明白
- 3挨个比，碰到第一个大于等于 target 的位置就是答案。能对，但要 O(n)。数组明明是升序的，这个条件白白浪费了。
- 4在升序数组里，一旦某个位置满足「nums[i] 大于等于 target」，它后面就全满足——这是一条从假到真、只翻一次的分界。二分要找的，就是这条分界的左端点。
- 5l=0，r=4（取 len，不是 len 减 1）l 从 0 开始，r 取数组长度 4——注意 r 能等于长度，因为答案可能是「插在最末尾」。现在要找第一个大于等于 2 的位置。
- 6mid =（0 加 4）整除 2 = 2取区间中点 mid=2，看到 nums[2]=5。拿它跟 target=2 比，决定收哪半边。
- 75 ≥ 2 → mid 是候选，收右边5 大于等于 2，说明 mid=2 这个位置满足条件，它有可能就是答案，但它右边的更大，更不可能。所以收右边——关键是 r 收到 mid 本身，不减 1，别把候选丢了。
- 8r = 2，区间缩成 [0, 2)r 收到 2，范围变成 [0, 2)。下标 2、3 变灰丢掉。mid 虽然是候选，但右边没有更优的，所以连它一起划到区间外。
- 9mid =（0 加 2）整除 2 = 1新区间 [0, 2)，中点 mid=1，看到 nums[1]=3。
- 103 ≥ 2 → 仍是候选，收 r=mid3 也大于等于 2，下标 1 仍然可能是答案。继续往左缩，r 收到 mid=1。
- 11r = 1，区间缩成 [0, 1)r 收到 1，范围 [0, 1)，现在只剩下标 0 没看过了。
- 12mid = 0 → nums[0] = 1 小于 2这轮走另一条分支：mid=0，nums[0]=1 比 target 小。1 排不到 2 前面，下标 0 不可能是插入位置。
- 13l = 1，此时 l == r，循环结束nums[mid] 太小，mid 和它左边全丢，l 跳到 mid 加 1 等于 1。现在 l 和 r 都是 1，区间空了，循环结束。
- 14答案 = l = 1收尾时 l 等于 1，就是答案：2 插在下标 1，数组变成 1、2、3、5、6 仍升序。无论 target 在不在数组里，返回的都是 l。
- 15[0,4) → [0,2) → [0,1) → l=1 停把三轮连起来看：每轮 mid 大于等于 2 就把 r 拉到 mid 保候选，mid 小于 2 就把 l 推过 mid。区间像夹子一样越夹越窄，最后 l 停在那条真假分界的左端，就是插入位置 1。
- 18只要能把问题改写成「第一个满足某条件的位置」，就是 lower_bound：满足时 r=mid 留候选、不满足时 l=mid+1 弃旧，最后返回 l。
- 20target=7，看 r 该不该取 lentarget=7 比谁都大，每轮 nums[mid] 都小于 7，l 一路被推到 4。如果当初把 r 写成 len 减 1 等于 3，这里就到不了 4，会漏掉「插在最后」。这就是 r 必须取 len 的原因。
- 24本题是 lower_bound 的原子操作。会了它，LC34 找左右边界就是跑两次；x 的平方根、第一个错误版本都是把 check 换一下。想系统练，去二分专题，或问问 AI 助教小欧「lower_bound 和 upper_bound 差在哪」。
⚠️ 容易写错的地方
✗ 错：找不到时返回 -1
✓ 对：返回 l，就是插入位置
本题求的是插入位置，target 不在时 l 正好停在该插入的下标。返回 -1 是把它当成了普通查找，直接做错
✗ 错：nums[mid] 大于等于 target 时写 r = mid - 1
✓ 对：r = mid（不减 1）
mid 自己可能就是第一个满足的位置，减 1 会把答案丢掉，结果偏小一格
✗ 错：r 初始化成 len(nums) - 1
✓ 对：r = len(nums)
target 比所有数都大时，插入位置是末尾 len，r 少 1 就够不到，会漏掉「插在最后」这种情况
完整代码（Python / C++ / Java）
Python
class Solution:
def searchInsert(self, nums, target):
l, r = 0, len(nums) # 半开 [l, r)
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1 # 太小，弃掉 mid 及左边
else:
r = mid # 候选，保留 mid
return l # 第一个 >= target 的位置C++
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size(); // 半开 [l, r)
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid; // 保留候选
}
return l;
}
};Java
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length; // 半开 [l, r)
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid; // 保留候选
}
return l;
}
}套路模板 · lower_bound 挖空骨架
# 找第一个满足 check 的位置；半开 [l, r)
l, r = 0, len(nums) # r 取 len，能表示「末尾」
while l < r: # 区间非空就继续
mid = l + (r - l) // 2
if check(mid): # 本题 check = nums[mid] >= target
r = mid # 满足，mid 是候选，留下
else:
l = mid + 1 # 不满足，弃掉 mid 及左边
return l # 第一个满足的位置（可能等于 len）// 找第一个满足 check 的位置；半开 [l, r)
int l = 0, r = (int)nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid; // 留候选
else l = mid + 1; // 弃旧
}
return l;// 找第一个满足 check 的位置；半开 [l, r)
int l = 0, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid; // 留候选
else l = mid + 1; // 弃旧
}
return l;复杂度
时间复杂度
O(log n)
每轮把候选区间砍掉一半，n 个数最多砍约 log n 刀就砍到空
空间复杂度
O(1)
全程只用 l、r、mid 三个变量，不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 搜索插入位置 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
半开区间 [l, r) 和闭区间 [l, r] 怎么选？+
都行，但循环条件和收缩规则必须配套。半开用 while l 小于 r、r=mid、返回 l；闭区间用 while l 小于等于 r、r=mid-1。lower_bound 用半开最顺，因为答案能取到 len。
如果数组里有重复的 target，返回哪一个？+
返回第一个 target 的下标。因为 nums[mid] 等于 target 时走的是 else 分支 r=mid，会一直往左收，最后停在最左边那个 target 上，正好是 lower_bound 的定义。
为什么 mid 写成 l + (r - l) // 2 而不是 (l + r) // 2？+
两者数学上相等，但 l+r 在 C++/Java 里可能整数溢出。l + (r - l) // 2 永远不会超过 r，更安全。Python 整数无上限，写哪个都行，但建议统一成防溢出写法。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。