【二分查找】LC 33.搜索旋转排序数组-平芜编程栈

文章目录

前言
一、题目
- 1、原题链接
- 2、题目描述
二、个人思路整理
- 1、思路分析
- 2、解题代码
三、知识风暴

前言
本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

33.搜索旋转排序数组

2、题目描述

二、个人思路整理

1、思路分析

本题的核心在于：旋转后的数组被任意mid切开后，一定有一半是有序的，另一半可能有序也可能包含旋转点。

具体步骤：

计算中点mid：若nums[mid] == target，直接返回mid。
判断哪半部分有序：

如果nums[left] <= nums[mid]：说明左半段[left, mid]是严格/单调升序的。
- 判断target是否落在左半段范围内，即nums[left] <= target && target < nums[mid]：
  - 若在：说明目标值在左半段，收缩右边界right = mid - 1；
  - 若不在：说明目标值在右半段，收缩左边界left = mid + 1。
否则（nums[left] > nums[mid]）：说明旋转点在左半段，右半段[mid, right]必然是有序的。
- 判断target是否落在右半段范围内，即nums[mid] < target && target <= nums[right]：
  - 若在：说明目标值在右半段，收缩左边界left = mid + 1；
  - 若不在：说明目标值在左半段，收缩右边界right = mid - 1。

退出循环：若left > right仍未找到，返回-1。

2、解题代码

classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;// 标准闭区间二分查找 [left, right]while(left<=right){// 防溢出写法计算中点intmid=left+(right-left)/2;// 命中目标值，直接返回下标if(nums[mid]==target){returnmid;}// 判断哪部分是有序的// 1. 如果 nums[left] <= nums[mid]，说明左半区间 [left, mid] 是单调递增的if(nums[left]<=nums[mid]){// 检查 target 是否落在有序的左半区间内if(nums[left]<=target&&target<nums[mid]){right=mid-1;// 目标在左侧，缩小右边界}else{left=mid+1;// 目标在右侧，缩小左边界}}else{// 2. 否则说明旋转断点在左侧，右半区间 [mid, right] 必然是有序的// 检查 target 是否落在有序的右半区间内if(nums[mid]<target&&target<=nums[right]){left=mid+1;// 目标在右侧，缩小左边界}else{right=mid-1;// 目标在左侧，缩小右边界}}}// 遍历结束未找到目标值return-1;}};

复杂度分析
时间复杂度：O ( log ⁡ n ) O(\log n)O(logn)，每次都将搜索区间减半。
空间复杂度：O ( 1 ) O(1)O(1)，仅使用常数个额外指针变量。

三、知识风暴

二分查找（Binary Search）是本题的核心思想。它通过不断折半缩小搜索区间，在有序数据中高效定位目标值。理解二分查找的区间定义、边界收缩与有序性判断，对掌握本题至关重要。

算法核心思想：

有序性前提：二分查找要求数据在逻辑上严格有序。本题的数组虽经旋转，但被任意mid切开后，一定有一半是严格升序的，我们正是利用这一半的有序性来决定收缩方向，从而在O ( log ⁡ n ) O(\log n)O(logn)时间内完成搜索。
折半搜索本质：每次取区间中点mid，先判断哪一半有序，再检查target是否落在该有序区间内，据此将搜索区间缩小一半，把时间复杂度从暴力遍历的O ( n ) O(n)O(n)降到O ( log ⁡ n ) O(\log n)O(logn)。
旋转数组的二分前提：与普通有序数组不同，旋转数组整体并非单调，因此不能直接套用经典二分模板，必须先定位有序半区，再决定向哪一侧收缩。

常见对比：二分查找 vs 暴力遍历

二分查找（Binary Search）：利用部分有序性每次排除一半区间，时间复杂度O ( log ⁡ n ) O(\log n)O(logn)，适合大规模数据的快速检索。
暴力遍历（线性扫描）：从头到尾扫描整个数组，时间复杂度O ( n ) O(n)O(n)，实现简单但效率低，无法满足本题对O ( log ⁡ n ) O(\log n)O(logn)的要求。
共同点：两者都能正确判断目标值是否存在。区别在于二分查找依赖有序性大幅减少比较次数，而暴力遍历不依赖任何数据特性、但代价是线性时间。

“区间边界”定义思想：

核心思想：二分查找的边界定义决定了循环条件与收缩方式。本题采用闭区间[left, right]，因此循环条件为left <= right，收缩时left = mid + 1或right = mid - 1，保证区间始终有效。
与本题的联系：本题初始区间为[0, n - 1]，每次比较中点元素后，先判断哪一半有序，再判断target是否落在有序半区内，据此收缩边界，直至区间为空仍未找到则返回-1。
注意事项：边界收缩必须严格跳过mid（即mid ± 1），否则可能陷入死循环；同时用left + (right - left) / 2计算中点可避免left + right整数溢出。

使用要点：

循环终止条件：闭区间写法下，当left > right时区间为空，说明目标不存在，退出循环返回-1。
单次迭代逻辑：计算mid = left + (right - left) / 2，若nums[mid] == target直接返回；否则判断nums[left] <= nums[mid]是否成立，以确定左半段是否有序，再决定收缩方向。
有序半区的判断：nums[left] <= nums[mid]成立说明左半段有序，此时只需检查target是否落在[nums[left], nums[mid])内即可决定收缩方向；否则右半段有序，检查target是否落在(nums[mid], nums[right]]内。
结果返回：一旦nums[mid] == target立即返回下标mid；若循环结束仍未命中，则说明目标不在数组中，返回-1。

算法变体与扩展：

搜索旋转排序数组 II（LeetCode 81）：数组中允许重复元素，此时nums[left] == nums[mid]无法判断哪半有序，需先收缩边界去重，是本题的直接进阶版。
寻找旋转排序数组中的最小值（LeetCode 153）：不搜索目标值，而是利用旋转点两侧的有序性二分定位最小值，是旋转数组二分的另一经典应用。
寻找峰值（LeetCode 162）：利用相邻元素大小关系在无序数组中二分定位峰值，体现二分思想不局限于严格有序数据。
在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）：通过两次二分分别定位左右边界，是二分查找处理重复元素的经典变体。

相关 LeetCode 例题：