[力扣_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]是有序

的，此时：

• 否则，说明

右侧区间[mid,right] 是有序的

，此时：

• 注意：区间收缩时不包含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;
}

本文链接：