91.搜索插入位置
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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] <= 104
- nums 为 无重复元素 的 升序 排列数组
- -104 <= target <= 104
思路
题目要求 O(log n)，所以线性扫描直接出局，必须二分。
容易把这题写成"先二分找，找到返回下标；找不到再想办法算插入位置"——分两套逻辑，代码又长又容易错。
真相是：这两种情况的答案完全统一。
换个说法就明白了：
▎ 答案 = 数组中小于 target 的元素个数。
验证一下：
┌───────────┬────────┬────────────────────┬──────┬──────┐ │ nums │ target │ 小于 target 的元素 │ 个数 │ 答案 │ ├───────────┼────────┼────────────────────┼──────┼──────┤ │ [1,3,5,6] │ 5 │ 1, 3 │ 2 │ 2 ✅ │ ├───────────┼────────┼────────────────────┼──────┼──────┤ │ [1,3,5,6] │ 2 │ 1 │ 1 │ 1 ✅ │ ├───────────┼────────┼────────────────────┼──────┼──────┤ │ [1,3,5,6] │ 7 │ 1,3,5,6 │ 4 │ 4 ✅ │ ├───────────┼────────┼────────────────────┼──────┼──────┤ │ [1,3,5,6] │ 0 │ 无 │ 0 │ 0 ✅ │ └───────────┴────────┴────────────────────┴──────┴──────┘
四种情况（含两个边界）全部对上，找到和没找到根本不需要区分。
再换一个等价说法，这个说法直接对应代码：
▎ 答案 = 第一个「大于等于 target」的元素的下标。（如果都小于 target，就是 n）
这个东西有个标准名字叫 lower_bound（下界查找），是二分查找里最重要的一个变体。本题就是 lower_bound 的裸题。
为什么最后返回 left
这是全题最需要理解的地方。用循环不变量来看：
整个循环过程中，这两条始终成立：
- left 左边的元素（下标 < left）全都 < target
- right 右边的元素（下标 > right）全都 >= target
循环在 left > right 时结束，此时必然是 left == right + 1，两个区域正好拼接、没有缝隙：
下标: [ 0 ... left-1 ] [ left ... n-1 ] 状态: 全都 < target 全都 >= target ↑ 分界点就在这，left 就是答案
所以 left 恰好是"第一个 ≥ target 的位置"，也恰好是"小于 target 的元素个数"。两种说法在这里合流了。
class Solution {
/**
* 搜索插入位置 —— lower_bound 二分查找
*
* 核心思想：找到与找不到其实是同一个问题 ——
* 答案 = 第一个 >= target 的元素下标 = 小于 target 的元素个数
*
* 循环不变量：
* left 左边（下标 < left）的元素全都 < target
* right 右边（下标 > right）的元素全都 >= target
* 循环结束时 left == right + 1，两区正好拼接，left 即为分界点
*
* 时间复杂度 O(log n)：区间每轮折半
* 空间复杂度 O(1)
*/
fun searchInsert(nums: IntArray, target: Int): Int {
// 闭区间 [left, right]，搜索范围包含两端
var left = 0
var right = nums.size - 1
// 闭区间的循环条件必须是 <= ：
// left == right 时区间里还剩一个元素，不能漏掉对它的检查
while (left <= right) {
// 写成 left + (right - left) / 2 而不是 (left + right) / 2，
// 后者在数组极长时 left + right 会整数溢出成负数 → 下标越界
val mid = left + (right - left) / 2
if (nums[mid] < target) {
// mid 太小，不可能是答案，答案在 mid 右边
left = mid + 1
} else {
// nums[mid] >= target：mid 有可能是答案，
// 但左边也许还有更靠前的，继续往左收缩
right = mid - 1
}
}
// 退出时 left 正好落在分界点上：
// 它左边全 < target，它及右边全 >= target
return left
}
}
复杂度
- 时间复杂度:
- 空间复杂度:
- 邮箱 ：charon.chui@gmail.com
- Good Luck!