搜索插入位置
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1
5 已存在于下标 2。示例 2
2 不存在，应插入到下标 1（在 1 与 3 之间）。示例 3
7 大于所有元素，应插入到末尾下标 4。模拟答题者思考
1. 我先想暴力：从左到右扫描，遇到 target 就返回下标，否则找到第一个比 target 大的位置——O(n)，但题目要求 O(log n)。
2. 重复在哪里？数组升序且无重复，任意时刻「答案」要么是 target 的下标，要么是第一个 >= target 的位置——这和普通二分查找的「排除一半」结构完全一致。
3. 关键转化：用标准二分维护 [l, r]；nums[mid] == target 直接返回；nums[mid] < target 则答案在右半 l = mid + 1，否则在左半 r = mid - 1。循环结束时 l 就是插入位置（lower bound）。
4. 例 [1,3,5,6], target=2：首轮 mid=1, nums[mid]=3 > 2 缩左；次轮 mid=0, nums[mid]=1 < 2 令 l=1；循环结束返回 l=1。
5. 每轮排除一半，O(log n)；也可理解为在升序数组上求 lower_bound(target)，命中与未命中统一由 l 表达。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
l, r | int | 定义：当前待搜索区间的左右边界下标 维护：答案下标（命中位置或插入位置）始终在 [l, r+1] 对应的搜索范围内更新：每轮根据 nums[mid] 与 target 的大小关系，将区间收缩一半 |
mid | int | 定义：当前区间中点下标 (l + r) // 2维护：将区间切成左段 [l, mid] 与右段 [mid+1, r]更新：每轮二分重新计算；若 nums[mid] == target 直接返回 mid |
插入位置 l | int | 定义：循环结束后 l 指向「第一个 >= target 的元素下标」，即 lower bound维护：数组升序且无重复， l 左侧元素均 < target，右侧（含 l）均 >= target更新：当 nums[mid] < target 时令 l = mid + 1，否则令 r = mid - 1；未命中时返回 l |
落码步骤
1. 初始化 l = 0、r = len(nums) - 1
2. 当 l <= r：取 mid = (l + r) // 2，若 nums[mid] == target 返回 mid
3. 若 nums[mid] < target，则 l = mid + 1（答案在右半）
4. 否则 r = mid - 1（答案在左半或就是 mid 左侧的插入位）
5. 循环结束返回 l（第一个 >= target 的下标，即插入位置）
代码实现
class Solution:
def searchInsert(self, nums: list[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1 # target 在右半
else:
r = mid - 1 # target 在左半或应插在此处
return l # lower bound：第一个 >= target 的下标class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
l = mid + 1; // target 在右半
else
r = mid - 1; // target 在左半或应插在此处
}
return l; // lower bound
}
};
// 时间 O(log n)，空间 O(1)复杂度分析
O(log n)
O(1)
常见坑
未命中时必须返回 l 而不是 r：循环结束时 l 是第一个 >= target 的位置，r 会落在其左侧。
target 大于所有元素时，l 会增至 len(nums)（如示例 3 返回 4），不要误以为越界——这正是「插入末尾」的正确答案。
与 #34 找左右边界不同，本题元素无重复，命中时可直接 return mid，无需继续向两侧搜索。
必测边界 Case
nums = [1,3,5,6], target = 5 → 2
nums = [1,3,5,6], target = 2 → 1
nums = [1,3,5,6], target = 7 → 4
nums = [1,3,5,6], target = 0 → 0
nums = [1], target = 0 → 0；nums = [1], target = 2 → 1