题目描述
升序数组中找 target，存在返回下标；不存在返回它按序应插入的位置。
nums = [1, 3, 5, 6]
target = 2
输出 = 1
思路解析
一个一个比是 O(n)。但数组有序——咱们可以用二分，降到 O(log n)。关键是把问题看成「找第一个 ≥ target 的位置」。
l、r 圈定可能区间。如果 mid 处 ≥ target，说明答案在 mid 或者更左边，r=mid；如果 mid < target，说明要往右找，l=mid+1。区间收到一个点，就是插入位置。
l=0, r=4：区间 [0,4)，mid=2 处是 5 ≥ 2，插入点不会在它右边，所以 r 收到 2。
l=0, r=2：区间 [0,2)，mid=1 处是 3 ≥ 2，继续收左，r=1。
l=0, r=1：区间 [0,1)，mid=0 处是 1 < 2，插入点在它右边，l=1。
收敛 · l==r：l 和 r 相遇在 1，区间收为一点。下标 1 就是 2 该插入的位置。
很多二分题其实都是「下界」：第一个 ≥ target、第一个为真……把判定条件想清楚，模板就能通用。
参考代码（Python）
Python
1l, r = 0, len(nums) # 右开区间 [l, r)
2while l < r:
3 mid = (l + r) // 2
4 if nums[mid] >= target: r = mid # 收右，保留mid
5 else: l = mid + 1 # 进左
6return l复杂度分析
- 时间复杂度：O(log n) —— 每次砍一半
- 空间复杂度：O(1) —— 几个指针
套路模板
记住骨架：左闭右开、满足收 r=mid、不满足 l=mid+1、返回 l。改一下条件就能解搜索插入、查找边界、旋转数组等一大类。
Python
1# 「找第一个满足 cond 的位置」都套
2l, r = 0, n # 左闭右开 [l, r)
3while l < r:
4 mid = (l + r) // 2
5 if cond(mid): r = mid # 满足，答案在 mid 或更左
6 else: l = mid + 1 # 不满足，往右
7return l # 第一个满足的位置易错点
- ❌ r = len(nums) - 1 → ✅ 右开区间用 r = len(nums)（插入位置可能在末尾，要能取到 n）
- ❌ 满足条件时 r = mid - 1 → ✅ 收 r = mid(保留 mid)（mid 本身可能就是答案，不能丢）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。