欢迎来到李耶的频道【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)
• 优势：逻辑分步清晰，将复杂问题拆解为"找旋转点 + 标准二分查找"

解法对比

扩展题

1. 搜索旋转排序数组 II：与本题相同，但数组可能包含重复元素，搜索指定目标值。
2. 寻找旋转排序数组中的最小值：寻找旋转排序数组中的最小元素。
3. 搜索二维矩阵：编写一个高效的算法来判断m x n矩阵中是否存在一个目标值，矩阵具有特性：每行每列均按升序排列。

“举一隅不以三隅反，则不复也。” —— 《论语·述而》

关注李耶，每天一道面试题，一起卷起来 🔥