0035. Search Insert Position¶
题目信息¶
- 题号:
搜索插入位置
- 难度:
Easy
- 主题:
数组、二分查找、下界
- 原题:
- 重点:
从精确查找与失败插入两种情况,推导到统一寻找第一个不小于目标的位置
题目重述¶
给定一个按严格递增顺序排列、元素互不相同的整数数组 nums 和整数 target。若 target 已经存在,返回
它的零基下标;若不存在,返回把它插入数组后仍保持严格递增的位置。
返回值可以等于 nums.size(),表示目标应插入数组末尾。题目要求时间复杂度为 O(log n)。
nums 的长度位于 [1, 10^4],数组元素和 target 均位于 [-10^4, 10^4]。
自建示例¶
目标已经存在:
nums = [2, 5, 9, 14]、target = 9,返回2;插入两个元素之间:
nums = [1, 4, 7, 10]、target = 6,返回2;插入数组开头:
nums = [3, 8, 12]、target = -2,返回0;插入数组末尾:
nums = [-3, 0, 8]、target = 12,返回3;单元素数组:
nums = [5]、target = 4,返回0;target = 6时返回1。
C++ 实现¶
#include <vector>
class Solution {
private:
int linearScan(const std::vector<int>& nums, int target) {
for (int index = 0; index < static_cast<int>(nums.size()); ++index) {
if (nums[index] >= target) {
return index;
}
}
return static_cast<int>(nums.size());
}
int exactSearchThenInsert(const std::vector<int>& nums, int target) {
int left = 0;
int right = static_cast<int>(nums.size()) - 1;
while (left <= right) {
const int middle = left + (right - left) / 2;
if (nums[middle] == target) {
return middle;
}
if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return left;
}
int lowerBound(const std::vector<int>& nums, int target) {
int left = 0;
int right = static_cast<int>(nums.size());
while (left < right) {
const int middle = left + (right - left) / 2;
if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}
public:
int searchInsert(std::vector<int>& nums, int target) {
return lowerBound(nums, target);
}
};
题解¶
线性下界¶
从左向右寻找第一个满足 nums[index] >= target 的位置:
该值等于目标时,当前位置就是目标下标;
该值大于目标时,目标应插入当前位置之前;
始终没有找到时,目标应插入数组末尾。
因此,题目中的查找与插入共享同一个答案定义:第一个不小于目标的位置,也就是目标的下界。
linearScan 直接实现该定义,但最坏需要读取全部元素,时间为 O(n)。
精确查找的终止边界¶
exactSearchThenInsert 先在闭区间 [left, right] 中执行普通二分。中点值小于目标时舍弃左半区;中点值大于
目标时舍弃右半区;命中目标时立即返回。
目标不存在时,循环终止于 left == right + 1。此时:
left左侧的元素都小于目标;left及其右侧的元素都大于目标,或者left == nums.size()。
所以失败后的 left 正好是插入位置。这一方法已经达到 O(log n),但命中目标仍是单独出口;若数组允许重复
值,它也只保证返回某个目标位置,而不是第一个目标位置。
统一下界¶
存在与不存在最终都可以改写为同一个边界:
lowerBound(target) = 第一个满足 nums[index] >= target 的位置
数组有序,因此条件 nums[index] >= target 随下标呈现先假后真的单调结构。lowerBound 不再询问中点是否
恰好等于目标,而是直接寻找真假分界。
搜索区间采用半开形式 [left, right),初始为 [0, n)。位置 n 虽然不能访问,却是合法答案,表示所有
元素都小于目标。
半开区间不变量¶
循环始终保持:
[0, left)中的元素都小于目标;[right, n)中的元素都不小于目标;真正的下界仍位于闭范围
[left, right]。
取 middle = left + (right - left) / 2:
nums[middle] < target时,中点及其左侧都不是答案,令left = middle + 1;nums[middle] >= target时,中点仍可能是最早满足位置,令right = middle。
两个分支都严格缩小区间,并且不丢失下界。等于目标时继续向左收缩,最终自然得到目标第一次出现的位置。
边界覆盖¶
半开区间模板同时覆盖全部返回情况:
目标小于最小值时,
right最终收缩到0;目标等于某个元素时,搜索停在该元素位置;
目标位于两个元素之间时,搜索停在右侧较大元素位置;
目标大于最大值时,
left最终推进到n。
以 nums = [1, 4, 7, 10]、target = 6 为例,第一次取中点 2,值 7 不小于目标,令
right = 2;第二次取中点 1,值 4 小于目标,令 left = 2。循环结束于下标 2,其左侧都
小于 6,而 nums[2] = 7 不小于 6,所以插入位置为 2。
代码演进¶
linearScan 直接寻找第一个不小于目标的位置,语义准确但没有利用数组有序性。
exactSearchThenInsert 用普通二分搜索目标,命中时返回,失败时利用终止后的 left 作为插入位置。
lowerBound 将命中与插入统一为一个单调边界,删除相等分支,并让位置 n 自然进入答案范围。公开入口采用该
方法,其循环不变量与题目要求直接对应,也能推广到包含重复值的有序数组。
复杂度分析¶
线性扫描最坏读取 n 个元素,时间复杂度为 O(n)。两种二分方法每轮至少舍弃一半候选位置,时间复杂度均为
O(log n)。三种方法都只维护常数个下标,工作空间为 O(1)。