35. 搜索插入位置
一句话套路手写 lower_bound,返回插入位
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
思路
时间
O(log n)空间
O(1)思路
就是 lower_bound —— 第一个 >= target 的下标。
循环不变式
答案始终在 [lo, hi] 内;while (lo <= hi) 退出时 lo == hi + 1,而 lo 就是插入点(模板 A 的这个出口条件背下来:闭区间 -> lo 落在第一个更大的位置)。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0035 {
class Solution {
public:
static int searchInsert(const vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
lo = mid + 1;
else
hi = mid - 1;
}
return lo; // 能走到这里说明 target 不存在,lo 就是第一个 > target 的下标 = 插入位
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0035::Solution s;
vector<int> a{1, 3, 5, 6};
CHECK_EQ(s.searchInsert(a, 5), 2);
CHECK_EQ(s.searchInsert(a, 2), 1);
CHECK_EQ(s.searchInsert(a, 7), 4); // 比所有都大
CHECK_EQ(s.searchInsert(a, 0), 0); // 比所有都小
vector<int> b{1};
CHECK_EQ(s.searchInsert(b, 1), 0);
CHECK_EQ(s.searchInsert(std::vector<int>{}, 3), 0); // 空数组