题目描述
思路解析
一句话答案：LeetCode 35 搜索插入位置：升序数组里找 target，在就返回下标，不在就返回它该插入的位置，本质是求第一个 ≥ target 的下标。二分每轮砍一半，mid 合格收 r=mid 留住候选，时间 O(log n)。
搜索插入位置到底要返回哪个下标
给一个升序、无重复的数组 nums 和目标值 target。target 在数组里就返回它的下标；不在就返回它该插入的位置。题面例子：nums=[1,3,5,6]、target=5 返回 2、target=2 返回 1。两种情形是同一个问题：都在问「第一个大于等于 target 的数排第几」，这个下标叫 lower_bound（第一个不小于目标的位置）。
一个个往后比，为什么对不起这个有序数组
挨个往后比，最坏要看遍 n 个数，是 O(n) 的线性扫。可数组明明升序，「≥ target」一旦成立往右就一直成立、左边一律不成立，线性扫把这条性质白扔了。一刀两断的结构，用二分查找在 O(log n) 里解决。
凭什么这个数组能二分
二分要成立，得有一条把区间劈两半的单调性质，这里就是「nums[i] ≥ target 吗」。数组升序，这个判断从某个位置起由「否」翻成「是」、再不翻回：左边全小于 target，右边全大于等于 target。插入位置就是这条分界线上「是」的第一个格子，每看一个中点砍掉一半。
mid 合格时，右界为什么收 mid 不收 mid−1
把范围定成左闭右开区间 [l, r)（含 l、不含 r），起手 l=0、r=n。r 取长度 n 而非 n−1，因为插到末尾时下标正好是 n。取中点 mid=(l+r)//2 比 target：nums[mid] ≥ target 时够大、可能是答案，右界收到 mid（写 r=mid 不是 mid−1，留住它）；nums[mid] < target 时它和左边全太小，左界写 l=mid+1 跳过。循环到 l==r，l 停处就是第一个 ≥ target 的下标。答案自始至终留在 [l, r) 里。
题面两个例子，逐轮收区间
先看 target=5、nums=[1,3,5,6]，l=0、r=4。第一轮 mid=2，nums[2]=5≥5，收 r=2，区间 [0,2)。第二轮 mid=1，nums[1]=3<5，收 l=2，区间 [2,2)。l==r=2 退出，返回 2。
再看不存在的 target=2。l=0、r=4。第一轮 mid=2，5≥2，r=2。第二轮 mid=1，3≥2，r=1。第三轮 mid=0，nums[0]=1<2，l=1，区间 [1,1)。l==r=1 退出，返回 1。
右界起手用 n−1，末尾那个位置就没了
右界起手写成 n−1 最常见：右开区间本就够不到下标 n，target 大过所有数、该插到末尾时就返回不出 n，末尾那个位置凭空没了。收缩写反也坑：nums[mid] ≥ target 时手滑写 r=mid−1，会把可能是答案的 mid 丢掉。循环条件要配对：左闭右开用 while l<r，错成 l<=r 又不动 r，l==r 那轮空转成死循环。mid 用 (l+r)//2 数值极大时会溢出，稳妥写 l+(r−l)//2。收尾复杂度：每轮把区间对半砍，最多 log₂n 次收空，时间 O(log n)；只用 l、r、mid 三个下标，空间 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「第一个 ≥ target 的位置 = 插入下标」，下面每一帧都在套它。
开始在有序数组里找「第一个 ≥ 7 的位置」。左界 l=0、右界 r=8（注意右界取数组长度 8，因为答案可能落到「末尾之后」）。
看中点 nums[4]=8，它 ≥ 7，说明这个位置「合格」（够大），它有可能就是答案；但更靠左也许还有合格的，得继续往左找。
因为 mid 自己也可能是答案，右界收到 mid（不是 mid-1）：r → 4。候选区间缩成 [0, 4)，灰格是已排除的。
看中点 nums[2]=5，它比 7 小，那它和它左边的数全都 < 7、统统不可能是答案，整片排除。
mid 已确定太小，左界直接跳过它：l → 3。候选区间缩成 [3, 4)。
看中点 nums[3]=6，它比 7 小，那它和它左边的数全都 < 7、统统不可能是答案，整片排除。
mid 已确定太小，左界直接跳过它：l → 4。候选区间缩成 [4, 4)。
区间收成一个点，l=4。target=7 不在数组里，但第一个 ≥ 它的数（nums[4]=8）顶上来了，target 就该插在这个下标，答案 4。
开始在有序数组里找「第一个 ≥ 10 的位置」。左界 l=0、右界 r=8（注意右界取数组长度 8，因为答案可能落到「末尾之后」）。
看中点 nums[4]=8，它比 10 小，那它和它左边的数全都 < 10、统统不可能是答案，整片排除。
mid 已确定太小，左界直接跳过它：l → 5。候选区间缩成 [5, 8)。
看中点 nums[6]=12，它 ≥ 10，说明这个位置「合格」（够大），它有可能就是答案；但更靠左也许还有合格的，得继续往左找。
因为 mid 自己也可能是答案，右界收到 mid（不是 mid-1）：r → 6。候选区间缩成 [5, 6)，灰格是已排除的。
看中点 nums[5]=10，它 ≥ 10，说明这个位置「合格」（够大），它有可能就是答案；但更靠左也许还有合格的，得继续往左找。
因为 mid 自己也可能是答案，右界收到 mid（不是 mid-1）：r → 5。候选区间缩成 [5, 5)，灰格是已排除的。
区间收成一个点，l=5，而 nums[5] 正好等于 10——target 存在，「第一个 ≥ target 的位置」就是它自己，答案 5。
开始在有序数组里找「第一个 ≥ 20 的位置」。左界 l=0、右界 r=8（注意右界取数组长度 8，因为答案可能落到「末尾之后」）。
看中点 nums[4]=8，它比 20 小，那它和它左边的数全都 < 20、统统不可能是答案，整片排除。
mid 已确定太小，左界直接跳过它：l → 5。候选区间缩成 [5, 8)。
看中点 nums[6]=12，它比 20 小，那它和它左边的数全都 < 20、统统不可能是答案，整片排除。
mid 已确定太小，左界直接跳过它：l → 7。候选区间缩成 [7, 8)。
看中点 nums[7]=15，它比 20 小，那它和它左边的数全都 < 20、统统不可能是答案，整片排除。
mid 已确定太小，左界直接跳过它：l → 8。候选区间缩成 [8, 8)。
所有数都比 20 小，区间一路向右收到末尾，l=8=数组长度，target 插到最后，答案 8。
边界先想清：太大插末尾(=长度)、太小插开头(0)、存在返回原位、空数组返回 0。
两个高频追问：下界二分天然处理重复（返回最左），改个符号就是上界。
参考代码
def searchInsert(nums, target): l, r = 0, len(nums) # r 取 n：插入位可到末尾之后 while l < r: mid = (l + r) // 2 if nums[mid] >= target: r = mid # mid 合格，留在候选内 else: l = mid + 1 # mid 太小，排除 return l # 第一个 >= target 的下标复杂度
- 时间：O(log n)，每轮把候选区间砍一半
- 空间：O(1)，只用 l、r、mid 三个下标，不开额外数组
易错点
面试追问把动画讲成自己的话
追问如果数组有重复元素，要返回 target 第一次出现的位置，代码要改吗？
追问如果要找「第一个 > target」的位置（上界 upper_bound）怎么改？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
x 的平方根
LeetCode 69 · 简单 · 沿着 二分查找 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题