当前位置：首页 > news >正文

【LeetCode】33.搜索旋转排序数组

news 2026/8/10 9:14:35

欢迎来到李耶的频道【LeetCode面试题】。

搜索旋转排序数组

33.搜索旋转排序数组

题目

整数数组nums按升序排列，数组中的值互不相同。

在传递给函数之前，nums在预先未知的某个下标k（0 <= k < nums.length）上进行了旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。

给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。

你必须设计一个时间复杂度为O(log n)的算法解决此问题。

输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

输入：nums = [1], target = 0 输出：-1

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums中的每个值都独一无二
nums肯定会在某个点上旋转
-10^4 <= target <= 10^4

解法一：二分查找（一次遍历）

思路：旋转排序数组从中间切开时，至少有一半是连续递增的。利用这一点，在二分查找中判断target是否落在有序的那一半，从而缩小搜索范围。关键步骤是判断[left, mid]区间是否有序。

functionsearch(nums,target){letleft=0;letright=nums.length-1;while(left<=right){constmid=Math.floor((left+right)/2);if(nums[mid]===target)returnmid;// 判断左半部分 [left, mid] 是否有序if(nums[left]<=nums[mid]){// 左半部分有序，判断 target 是否在左半部分范围内if(nums[left]<=target&&target<nums[mid]){right=mid-1;// 在左半部分查找}else{left=mid+1;// 在右半部分查找}}else{// 右半部分 [mid, right] 有序if(nums[mid]<target&&target<=nums[right]){left=mid+1;// 在右半部分查找}else{right=mid-1;// 在左半部分查找}}}return-1;}

时间复杂度 / 空间复杂度：O(log n) / O(1)
优势：一次遍历完成查找，空间 O(1)，是面试中最推荐的写法

解法二：先找旋转点，再二分查找

思路：先通过二分查找找到数组的最小元素（旋转点），将数组划分为两个有序部分。然后根据target的值决定在哪个有序部分进行标准二分查找。

functionsearch(nums,target){constn=nums.length;if(n===0)return-1;// 1. 二分查找找旋转点（最小值下标）letleft=0;letright=n-1;while(left<right){constmid=Math.floor((left+right)/2);if(nums[mid]>nums[right]){left=mid+1;}else{right=mid;}}constpivot=left;// 2. 确定 target 在哪个有序区间letl,r;if(target>=nums[pivot]&&target<=nums[n-1]){l=pivot;r=n-1;}else{l=0;r=pivot-1;}// 3. 标准二分查找while(l<=r){constmid=Math.floor((l+r)/2);if(nums[mid]===target)returnmid;if(nums[mid]<target){l=mid+1;}else{r=mid-1;}}return-1;}

时间复杂度 / 空间复杂度：O(log n) / O(1)
优势：逻辑分步清晰，将复杂问题拆解为"找旋转点 + 标准二分查找"

解法对比

解法	时间 / 空间复杂度	优势	推荐指数
二分查找（一次遍历）	O(log n) / O(1)	代码简洁，一次遍历完成	⭐⭐⭐⭐⭐
先找旋转点再二分	O(log n) / O(1)	分步逻辑清晰，易于理解	⭐⭐⭐⭐