LeetCode LCR 068. 搜索插入位置
题目描述
题意分析
在升序且无重复元素的数组中查找目标值：存在时返回它的下标，不存在时返回插入后仍保持升序的位置。
两种情况可以统一为寻找第一个大于等于
target的位置；如果所有元素都小于它，答案就是数组长度n，表示追加到末尾。排序保证判定nums[i] >= target从假到真最多变化一次，可以用二分定位这个分界。
解法：二分第一个不小于目标的位置
核心思路
[!blue]
初始化
left = 0、right = n。始终保持：下标小于left的元素都小于目标，下标大于等于right的实际元素都大于等于目标；还没确定类别的元素位于半开区间[left, right)。与此同时，待返回的分界位置位于闭区间
[left, right]。答案可以等于右边界，即使right = n不是可访问的数组下标，它仍是合法的插入位置。应区分“需要继续比较的元素范围”和“分界可能所在的位置”。当
left < right时取中点mid，有left <= mid < right <= n，所以nums[mid]一定可以访问：
- 若
nums[mid] >= target，有序性保证从mid往右的元素都符合条件，最早位置不会在其右侧。令right = mid，把这一段归入已知的大于等于部分，同时保留mid作为可能的答案。- 若
nums[mid] < target，从left到mid都小于目标，不可能成为答案。令left = mid + 1，把这一段归入已知的小于部分。两个分支都保持上述分类并缩短待检查区间。最终
left == right时，半开区间已经为空：左边全部小于目标，右边全部大于等于目标，这个唯一边界就是所求位置。目标小于所有元素时，边界会收敛到 $0$；目标大于所有元素时会收敛到
n。返回边界即可，不应再读取nums[left]，因为left = n时并没有对应元素。
解题步骤
- 令
left = 0、right = nums.length，将末尾插入位置也纳入可能答案。- 在
left < right时取中点mid。- 若
nums[mid] >= target，令right = mid；否则令left = mid + 1。- 待检查区间为空时，返回
left。
代码实现
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
func searchInsert(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
mid := (left + right) >> 1
if nums[mid] >= target {
right = mid
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，每轮将待检查区间缩小约一半，直到没有待比较元素。
- 空间复杂度：$O(1)$，只使用左右边界和中点。
关键点总结
[!green]
- 目标存在与不存在都对应第一个不小于目标的分界位置。
- 元素待查区间为
[left, right)，分界答案的候选范围为[left, right]，二者不能混写。- 满足条件的
mid保留为右边界，不满足的mid连同左侧排除。n是合法返回值，但不是可读取的元素下标。
易错点总结
[!yellow]
- 当前模板把
right初始化为n - 1，会丢掉返回n的末尾插入情况。- 满足条件时写成
right = mid - 1，可能越过恰好就是答案的mid。- 不满足条件时写成
left = mid，在只剩一个待查元素时无法推进。- 返回前再读取
nums[left]，会在目标大于所有元素时越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 同样查找有序数组的边界，本题只找第一个不小于目标的位置，原题还需找到最后一次出现。 |
| 704. 二分查找 | 简单 | 原题只判断目标是否存在，本题不存在时也要返回唯一插入位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！