0034. Find First and Last Position of Element in Sorted Array ============================================================ 题目信息 -------- :题号: 0034. 在排序数组中查找元素的第一个和最后一个位置 :难度: Medium :主题: 数组、二分查找、边界定位 :原题: `LeetCode 0034 `_ :重点: 从找到任意目标位置,推导到分别寻找第一个不小于目标和第一个大于目标的位置 题目重述 -------- 给定一个按非递减顺序排列的整数数组 ``nums`` 和整数 ``target``,返回目标值第一次与最后一次出现的零基下标, 结果格式为 ``[first, last]``。 若 ``target`` 不在数组中,返回 ``[-1, -1]``。算法必须达到 ``O(log n)`` 时间复杂度。 ``nums`` 的长度位于 ``[0, 10^5]``,数组元素和 ``target`` 均位于 ``[-10^9, 10^9]``。数组中允许存在 重复值;由于数组有序,所有等于 ``target`` 的元素必然构成一个连续区间。 自建示例 -------- * 重复段位于中间:``nums = [1, 2, 2, 2, 2, 5, 8]``、``target = 2``,返回 ``[1, 4]``; * 目标只出现一次:``nums = [-3, 0, 4, 7]``、``target = 4``,返回 ``[2, 2]``; * 整个数组都是目标:``nums = [6, 6, 6, 6]``、``target = 6``,返回 ``[0, 3]``; * 目标位于插入位置但并不存在:``nums = [1, 3, 5, 7]``、``target = 4``,返回 ``[-1, -1]``; * 空数组:``nums = []``、``target = 9``,返回 ``[-1, -1]``。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: std::vector linearScan(const std::vector& nums, int target) { int first = -1; int last = -1; for (int index = 0; index < static_cast(nums.size()); ++index) { if (nums[index] < target) { continue; } if (nums[index] > target) { break; } if (first == -1) { first = index; } last = index; } return {first, last}; } std::vector binaryThenExpand(const std::vector& nums, int target) { int low = 0; int high = static_cast(nums.size()) - 1; int found = -1; while (low <= high) { const int mid = low + (high - low) / 2; if (nums[mid] == target) { found = mid; break; } if (nums[mid] < target) { low = mid + 1; } else { high = mid - 1; } } if (found == -1) { return {-1, -1}; } int first = found; int last = found; while (first > 0 && nums[first - 1] == target) { --first; } while (last + 1 < static_cast(nums.size()) && nums[last + 1] == target) { ++last; } return {first, last}; } int lowerBound(const std::vector& nums, int target) { int low = 0; int high = static_cast(nums.size()); while (low < high) { const int mid = low + (high - low) / 2; if (nums[mid] < target) { low = mid + 1; } else { high = mid; } } return low; } int upperBound(const std::vector& nums, int target) { int low = 0; int high = static_cast(nums.size()); while (low < high) { const int mid = low + (high - low) / 2; if (nums[mid] <= target) { low = mid + 1; } else { high = mid; } } return low; } std::vector boundaryBinarySearch(const std::vector& nums, int target) { const int first = lowerBound(nums, target); if (first == static_cast(nums.size()) || nums[first] != target) { return {-1, -1}; } const int afterLast = upperBound(nums, target); return {first, afterLast - 1}; } public: std::vector searchRange(std::vector& nums, int target) { return boundaryBinarySearch(nums, target); } }; 题解 ---- 线性扫描 ~~~~~~~~ 最直接的方法从左到右检查数组。第一次遇到 ``target`` 时记录 ``first``,之后每次遇到目标都更新 ``last``。 数组有序,因此: * 当前值小于目标时继续向右; * 当前值等于目标时记录边界; * 当前值大于目标后,右侧只会更大,可以立即停止。 ``linearScan`` 准确表达了题目要求,也直接利用了目标值连续出现这一事实。不过当目标位于数组末尾或整个数组都等于 目标时,仍要读取 ``n`` 个元素,时间为 ``O(n)``,不能满足题目的对数要求。 普通二分与线性扩展 ~~~~~~~~~~~~~~~~~~ 普通二分能够在 ``O(log n)`` 时间内找到某个等于 ``target`` 的位置,但遇到相等时立即返回,不能保证该位置是重复 段的左端或右端。 ``binaryThenExpand`` 先二分得到下标 ``found``,再从这里分别向左和向右移动,直到相邻元素不再等于目标。 重复段长度为 ``r`` 时,扩展仍需要 ``O(r)`` 次操作。 若数组全部由目标值组成,二分虽然很快命中中间位置,随后仍要走到数组两端,总时间退化为 ``O(n)``。瓶颈已经 从“寻找目标”转移到“逐个穿过重复段”,因此边界本身也必须通过二分直接定位。 单调边界条件 ~~~~~~~~~~~~ 边界二分不再询问“中点是否等于目标”,而是寻找某个单调条件第一次成立的位置。 左边界对应: .. code-block:: text nums[index] >= target 在有序数组中,这个条件沿下标方向呈现为一段 ``false`` 后跟一段 ``true``。第一个成立的位置就是 ``lowerBound(target)``,即第一个不小于目标的下标。 右边界之后的位置对应: .. code-block:: text nums[index] > target 第一个成立的位置是 ``upperBound(target)``,即第一个严格大于目标的下标。记它为 ``afterLast``,重复段右端 就是 ``afterLast - 1``。 直接搜索“严格大于”比搜索 ``target + 1`` 更准确,也不依赖整数加一,因此不会在目标达到整数上界时产生溢出。 半开区间不变量 ~~~~~~~~~~~~~~ ``lowerBound`` 与 ``upperBound`` 都在半开区间 ``[low, high)`` 中搜索,并允许答案等于 ``nums.size()``。 对 ``lowerBound``,循环始终保持: * ``[0, low)`` 中的值都严格小于 ``target``; * ``[high, n)`` 中的位置都满足值不小于 ``target``; * 第一个满足条件的位置仍位于 ``[low, high]``。 若 ``nums[mid] < target``,中点及其左侧都不满足条件,令 ``low = mid + 1``。否则中点仍可能是第一个满足位置, 令 ``high = mid``。当 ``low == high`` 时,唯一候选就是左边界。 ``upperBound`` 使用相同的区间结构,只把不满足条件的范围改为 ``nums[mid] <= target``。所有相等元素会被排除到 左侧,搜索最终停在重复段之后。 目标区间 ~~~~~~~~ 非递减顺序保证数组可以按目标值划分为: .. code-block:: text 小于 target | 等于 target | 大于 target ``lowerBound`` 定位第二段起点,``upperBound`` 定位第三段起点。若 ``lowerBound`` 越过数组,或该位置的值不等于 目标,第二段为空,答案就是 ``[-1, -1]``。 目标存在时,两次边界之间的元素全部等于目标,所以答案直接为: .. code-block:: text [lowerBound(target), upperBound(target) - 1] 不需要再检查重复段中的任何元素。 状态演化 ~~~~~~~~ 对 ``nums = [1, 2, 2, 2, 2, 5, 8]``、``target = 2``: .. list-table:: :header-rows: 1 * - 搜索 - ``low`` - ``mid`` - ``high`` - 中点值 - 更新 * - ``lowerBound`` - 0 - 3 - 7 - 2 - ``high = 3`` * - ``lowerBound`` - 0 - 1 - 3 - 2 - ``high = 1`` * - ``lowerBound`` - 0 - 0 - 1 - 1 - ``low = 1``,得到 ``first = 1`` * - ``upperBound`` - 0 - 3 - 7 - 2 - ``low = 4`` * - ``upperBound`` - 4 - 5 - 7 - 5 - ``high = 5`` * - ``upperBound`` - 4 - 4 - 5 - 2 - ``low = 5``,得到 ``afterLast = 5`` 最终区间为 ``[first, afterLast - 1] = [1, 4]``。 代码演进 ~~~~~~~~ ``linearScan`` 逐个读取元素并直接维护首尾位置,正确但没有利用边界条件的单调性。 ``binaryThenExpand`` 用普通二分删除了寻找任意目标位置的线性工作,但向两侧扩展仍会逐个穿过重复段。它说明 “命中即停止”的二分语义太弱,必须让搜索继续逼近边界。 ``boundaryBinarySearch`` 分别寻找第一个 ``>= target`` 与第一个 ``> target`` 的位置,删除命中后的线性扩展。 公开入口采用该方法,两次搜索都只保留可能包含边界的一半区间。 复杂度分析 ~~~~~~~~~~ ``linearScan`` 的时间复杂度为 ``O(n)``。``binaryThenExpand`` 先用 ``O(log n)`` 找到一个目标,再用 ``O(r)`` 穿过长度为 ``r`` 的重复段,最坏仍为 ``O(n)``。 边界方法执行两次二分,每次把搜索区间至少缩小一半,时间复杂度为 ``O(log n)``;只使用固定数量的下标变量, 额外空间为 ``O(1)``。返回结果不计入工作空间。