[力扣_33] 搜索旋转排序数组
题目入口:点击进入
相关算法:
- 二分搜索——时间复杂度O(logn),空间复杂度O(1)
思路和算法:
题目要求时间复杂度为O(logn),显然应该使用二分查找,二分查找的过程就是不断收缩左右边界,而怎么缩小区间是关键
如果数组[未旋转],依旧保持有序,在数组中查找一个特点元素target的过程为:
- 若target == nums[mid],直接返回
- 若target < nums[mid],则target位于左侧区间 [left,mid) 中,令 right = mid-1,在左侧区间查找
- 若target > nums[mid],则target位于右侧区间(mid,right]中,令left = mid+1,在右测区间查找
显然,上述是一个二分搜索的通用思路,若不太了解,我们可以拿一个简单的有序数组来看看。
但是,这道题,由于数组 [被旋转] ,所以左侧或者右侧区间不一定是连续的,换句话说,这个数组只能是部分有序,在这种情况下,如何判断 target 位于哪个区间?
二分查找
根据旋转数组的特性,当元素不重复时,如果nums[i]<=nums[j],说明区间[i,j]是有序的。
- i、j 可以重合,所以这里使用的比较运算符是[小于等于]
因此,在旋转排序数组中查找一个特点元素时:
-
若 target == nums[mid] ,直接返回
-
若
nums[left] <= nums[mid]
,说明
左侧区间[left,mid]是有序
的,此时:
- 若nums[left] <= target <= nums[mid], 说明 target 在此区间内,则将边界搜索至 right = mid -1,在左侧区间查找
- 否则,则代表 target 位于 右边无序的序列中,我们需要在右边区间内查找 则 left =mid+1
-
否则,说明
右侧区间[mid,right] 是有序的
,此时:
- 若nums[mid] <= target <= nums[right] ,说明 target 位于右侧区间内,令left = mid +1 在右测区间查找
- 否则,令 right =mid -1 在左侧区间内查找
- 注意:区间收缩时不包含mid,也就是说,实际收缩后的区间是[left,mid)或者(mid,right]
上述定义是一个递归式的定义,可以拿一个示例去演示一遍,则会发现每一次的边界收缩,都会划分出一个有序或者两个有序的区间。
代码如下所示:
int search(int* nums, int numsSize, int target){
if(numsSize==0) return -1;
if(numsSize==1) return nums[0]==target?0:-1;
int left=0;
int right=numsSize-1;
int med=right/2;
while(left < right)
{
//printf("nums[%d]=%d,nums[%d]=%d,nums[%d]=%d\n",med,nums[med],left,nums[left],right,nums[right]);
if(nums[med]==target) return med;
if(nums[left]==target) return left;
if(nums[right]==target) return right;
if(nums[left]<nums[med])
{
if(nums[left]<target&&nums[med]>target)
{
right=med-1;
med=(right+left)/2;
}
else{
left=med+1;
med=(left+right)/2;
}
}
else
{
if(nums[med]<target&&nums[right]>target)
{
left=med+1;
med=(left+right)/2;
}
else{
right=med-1;
med=(right+left)/2;
}
}
}
return -1;
}