0035. Search Insert Position ============================ 题目信息 -------- :题号: 0035. 搜索插入位置 :难度: Easy :主题: 数组、二分查找、下界 :原题: `LeetCode 0035 `_ :重点: 从精确查找与失败插入两种情况,推导到统一寻找第一个不小于目标的位置 题目重述 -------- 给定一个按严格递增顺序排列、元素互不相同的整数数组 ``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++ 实现 -------- .. code-block:: cpp #include class Solution { private: int linearScan(const std::vector& nums, int target) { for (int index = 0; index < static_cast(nums.size()); ++index) { if (nums[index] >= target) { return index; } } return static_cast(nums.size()); } int exactSearchThenInsert(const std::vector& nums, int target) { int left = 0; int right = static_cast(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& nums, int target) { int left = 0; int right = static_cast(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& 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)``,但命中目标仍是单独出口;若数组允许重复 值,它也只保证返回某个目标位置,而不是第一个目标位置。 统一下界 ~~~~~~~~ 存在与不存在最终都可以改写为同一个边界: .. code-block:: text 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)``。