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

欢迎来到李耶的频道【LeetCode面试题】。搜索旋转排序数组33.搜索旋转排序数组题目整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了旋转使数组变为[nums[k], nums[k1], ..., 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^4nums中的每个值都独一无二nums肯定会在某个点上旋转-10^4 target 10^4解法一二分查找一次遍历思路旋转排序数组从中间切开时至少有一半是连续递增的。利用这一点在二分查找中判断target是否落在有序的那一半从而缩小搜索范围。关键步骤是判断[left, mid]区间是否有序。functionsearch(nums,target){letleft0;letrightnums.length-1;while(leftright){constmidMath.floor((leftright)/2);if(nums[mid]target)returnmid;// 判断左半部分 [left, mid] 是否有序if(nums[left]nums[mid]){// 左半部分有序判断 target 是否在左半部分范围内if(nums[left]targettargetnums[mid]){rightmid-1;// 在左半部分查找}else{leftmid1;// 在右半部分查找}}else{// 右半部分 [mid, right] 有序if(nums[mid]targettargetnums[right]){leftmid1;// 在右半部分查找}else{rightmid-1;// 在左半部分查找}}}return-1;}时间复杂度 / 空间复杂度O(log n) / O(1)优势一次遍历完成查找空间 O(1)是面试中最推荐的写法解法二先找旋转点再二分查找思路先通过二分查找找到数组的最小元素旋转点将数组划分为两个有序部分。然后根据target的值决定在哪个有序部分进行标准二分查找。functionsearch(nums,target){constnnums.length;if(n0)return-1;// 1. 二分查找找旋转点最小值下标letleft0;letrightn-1;while(leftright){constmidMath.floor((leftright)/2);if(nums[mid]nums[right]){leftmid1;}else{rightmid;}}constpivotleft;// 2. 确定 target 在哪个有序区间letl,r;if(targetnums[pivot]targetnums[n-1]){lpivot;rn-1;}else{l0;rpivot-1;}// 3. 标准二分查找while(lr){constmidMath.floor((lr)/2);if(nums[mid]target)returnmid;if(nums[mid]target){lmid1;}else{rmid-1;}}return-1;}时间复杂度 / 空间复杂度O(log n) / O(1)优势逻辑分步清晰将复杂问题拆解为找旋转点 标准二分查找解法对比解法时间 / 空间复杂度优势推荐指数二分查找一次遍历O(log n) / O(1)代码简洁一次遍历完成⭐⭐⭐⭐⭐先找旋转点再二分O(log n) / O(1)分步逻辑清晰易于理解⭐⭐⭐⭐扩展题搜索旋转排序数组 II与本题相同但数组可能包含重复元素搜索指定目标值。寻找旋转排序数组中的最小值寻找旋转排序数组中的最小元素。搜索二维矩阵编写一个高效的算法来判断m x n矩阵中是否存在一个目标值矩阵具有特性每行每列均按升序排列。“举一隅不以三隅反则不复也。” —— 《论语·述而》关注李耶每天一道面试题一起卷起来