搜索插入位置
Search Insert Position
在有序数组中查找 target：存在返回下标，不存在返回它应该插入的位置。
在力扣中练习题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
解题思路
二分 · 找插入点
区间缩到空时，left 就是第一个不小于 target 的位置
这题本质上是 lower_bound：找第一个大于等于 target 的位置。标准二分用闭区间 [left, right]，每次比较 nums[mid]：
- 等于 target：直接返回 mid；
- 小于 target：答案在右边，
left = mid + 1； - 大于 target：答案在左边，
right = mid - 1。
在 [1,3,5,5,7,9] 中找 6；它不存在，最终要返回第一个大于它的下标。
循环结束的条件是 left > right。此时所有小于 target 的元素都在 left 左边，left 指向第一个大于 target 的元素，正好是插入位置。
自拟数组有重复的 5，target 6 不存在。最后 left 停在 7 的下标 4，而不是末尾。题目只要求返回一个合法位置，但如果要求第一个匹配，需要在相等时继续向左收缩。
mid=4 是 7，太大，排除右半边；新区间 [3,3]。
- left
- 3
- right
- 3
时间 O(log n)，空间 O(1)。
易错点
- 循环结束后返回 right：right 是最后一个小于 target 的位置，差 1。
- mid 写成 (left+right)/2：left+right 可能溢出。
- 区间写成左闭右开却仍用 <=：会多比较一个越界位置。
lower_bound · 标准库
直接调用 C++ 的 lower_bound
一行代码且经过充分优化，但面试中通常要求手写二分；只适合作为结果对照。
std::lower_bound 在有序区间上返回第一个不小于 target 的迭代器。减去 begin() 就得到下标：
- 找到相等元素时返回第一个相等的位置；
- 没有相等元素时返回第一个更大的位置；
- 全部更小时返回
end()，下标等于 n。
它的复杂度同样是 O(log n)，但不同实现细节由标准库保证。面试里可以用它验证手写二分的结果，不建议作为唯一答案。
- 1调用 lower_bound(nums, target)。
- 2迭代器减去 begin() 得到下标。
- 3返回该下标。
易错点
- 用 upper_bound：返回的是第一个大于 target 的位置，和本题“存在时返回下标”不一致。
- 对无序数组调用：结果是未定义的。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [1,3,5,5,7,9]，target = 6在 [1,3,5,5,7,9] 中找 6；它不存在，最终要返回第一个大于它的下标。
查看 C++ 代码
延伸阅读
- lower_bound / upper_bound 的区别是“第一个 >=”还是“第一个 >”，重复元素题要特别确认。
- 插入位置、第一个错误版本、搜索旋转数组都可以用同一套闭区间二分模板。