[力扣_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,在右测区间查找

显然,上述是一个二分搜索的通用思路,若不太了解,我们可以拿一个简单的有序数组来看看。

img

但是,这道题,由于数组 [被旋转]所以左侧或者右侧区间不一定是连续的,换句话说,这个数组只能是部分有序,在这种情况下,如何判断 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]

    上述定义是一个递归式的定义,可以拿一个示例去演示一遍,则会发现每一次的边界收缩,都会划分出一个有序或者两个有序的区间。

    img

    代码如下所示:

    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;
    }

    本文链接:

    https://nullcode.fun/80.html
    1 + 5 =
    快来做第一个评论的人吧~