0033. Search in Rotated Sorted Array ==================================== 题目信息 -------- :题号: 0033. 搜索旋转排序数组 :难度: Medium :主题: 数组、二分查找、旋转有序数组 :原题: `LeetCode 0033 `_ :重点: 从线性扫描推导到识别单调半区,并在不显式寻找旋转点的情况下完成二分查找 题目重述 -------- 给定一个元素互不相同的整数数组 ``nums``。它原本按严格递增顺序排列,随后可能在某个位置旋转:把原数组的一个 后缀移动到开头,两个部分内部的相对顺序保持不变。 再给定整数 ``target``。若目标值存在,返回它在旋转后数组中的零基下标;否则返回 ``-1``。题目要求时间复杂度为 ``O(log n)``。 旋转后整个数组不再单调,但仍由至多两段严格递增区间组成。``nums`` 的长度位于 ``[1, 5000]``,元素值和 ``target`` 位于 ``[-10^4, 10^4]``。 自建示例 -------- * 目标位于左段:``nums = [8,10,13,1,3,5,6]``、``target = 10``,返回 ``1``; * 目标位于右段:``nums = [15,18,2,4,7,11]``、``target = 7``,返回 ``4``; * 数组未旋转:``nums = [2,5,9,12]``、``target = 9``,返回 ``2``; * 目标不存在:``nums = [5,7,9,12,1,3]``、``target = 8``,返回 ``-1``; * 单个元素:``nums = [4]``、``target = 3``,返回 ``-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 -1; } int binarySearch( const std::vector& nums, int target, int left, int right ) { 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 -1; } int findPivotThenSearch(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] > nums[right]) { left = middle + 1; } else { right = middle; } } const int pivot = left; const int last = static_cast(nums.size()) - 1; if (nums[pivot] <= target && target <= nums[last]) { return binarySearch(nums, target, pivot, last); } return binarySearch(nums, target, 0, pivot - 1); } int onePassBinarySearch(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[left] <= nums[middle]) { if (nums[left] <= target && target < nums[middle]) { right = middle - 1; } else { left = middle + 1; } } else { if (nums[middle] < target && target <= nums[right]) { left = middle + 1; } else { right = middle - 1; } } } return -1; } public: int search(std::vector& nums, int target) { return onePassBinarySearch(nums, target); } }; 题解 ---- 线性搜索基线 ~~~~~~~~~~~~ ``linearScan`` 从左到右检查每个位置。元素互异,所以第一次发现 ``target`` 就是唯一答案;扫描结束仍未发现则返回 ``-1``。该方法直接覆盖全部位置,时间复杂度为 ``O(n)``。 普通无序数组只能逐个排除,但旋转数组只打断了原递增数组中的一个相邻关系。它仍可写成两段严格递增序列: .. code-block:: text [8, 10, 13] | [1, 3, 5, 6] 顺序信息并未消失,关键是利用它一次排除一半候选。 旋转点二分 ~~~~~~~~~~ 一种直接做法是先找到最小值位置 ``pivot``,再在两段递增区间中选择一段做普通二分。 搜索旋转点时比较 ``nums[middle]`` 与 ``nums[right]``: * ``nums[middle] > nums[right]``,中点位于较大的左段,最小值只能在右侧; * 否则中点位于包含最小值的右段,旋转点可能就是 ``middle``。 每轮都保留旋转点所在的一半,最终 ``left == right`` 时得到最小值位置。未旋转数组也适用,此时区间会收缩到 下标 ``0``。 找到旋转点后,``[pivot,n-1]`` 与 ``[0,pivot-1]`` 都严格递增。根据目标是否落在 ``[nums[pivot],nums[n-1]]`` 中选择一段,再执行普通二分。该方法由两次 ``O(log n)`` 搜索组成,总复杂度仍为 ``O(log n)``。 单调半区 ~~~~~~~~ 搜索目标不必知道旋转点的精确下标。考虑当前候选区间 ``[left,right]``:它至多包含一个旋转断点,中点把区间 分开后,断点不可能同时位于两边内部,因此至少一半严格递增。 元素互异时可以用端点识别单调半区: * ``nums[left] <= nums[middle]``,左半区 ``[left,middle]`` 有序; * 否则旋转点位于左半区,右半区 ``[middle,right]`` 有序。 二分查找真正需要的不是整段数组有序,而是每轮至少有一半能够通过端点值域判断目标是否属于其中。 值域排除 ~~~~~~~~ 中点已经先与目标比较,因此后续区间不再包含 ``middle``。 左半区有序时,其值域为 ``[nums[left],nums[middle]]``: .. code-block:: text nums[left] <= target < nums[middle] 成立时,目标若存在只能位于 ``[left,middle-1]``;否则左半区可以整体排除,保留 ``[middle+1,right]``。 右半区有序时,对称判断: .. code-block:: text nums[middle] < target <= nums[right] 成立时保留 ``[middle+1,right]``;否则保留 ``[left,middle-1]``。 循环始终维护不变量:若目标存在,其下标位于 ``[left,right]``。每轮先检查中点,再利用一个已确认有序的半区和 端点值域排除不可能包含目标的一侧,因此不会丢失答案。 以 ``nums = [4,5,6,7,0,1,2]``、``target = 2`` 为例: .. list-table:: :header-rows: 1 * - 候选区间 - 中点 - 有序半区 - 保留区间 * - ``[0,6]`` - 下标 3,值 7 - 左半 ``[4,5,6,7]`` - 2 不在 ``[4,7)``,保留 ``[4,6]`` * - ``[4,6]`` - 下标 5,值 1 - 左半 ``[0,1]`` - 2 不在 ``[0,1)``,保留 ``[6,6]`` * - ``[6,6]`` - 下标 6,值 2 - 中点命中 - 返回 6 重复值限制 ~~~~~~~~~~ 单调半区的识别依赖元素互异。若允许大量重复值,例如 ``[1,0,1,1,1]``,当 ``left``、``middle``、``right`` 对应值都为 ``1`` 时,仅凭端点无法判断旋转点位于哪一侧,只能逐步缩小边界,最坏可能退化为线性。 本题排除重复值,因此 ``nums[left] <= nums[middle]`` 能可靠确认左半区有序;每轮都能舍弃约一半候选。 复杂度分析 ~~~~~~~~~~ ``linearScan`` 最坏检查 ``n`` 个元素,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。 ``findPivotThenSearch`` 进行两次二分,时间复杂度为 ``O(log n)``,额外空间为 ``O(1)``。 ``onePassBinarySearch`` 每轮保留至多一半候选,时间复杂度为 ``O(log n)``;只维护三个下标,额外空间为 ``O(1)``。公开入口采用该方法。