[力扣_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;
}