leetcdoe 33. 搜索旋转排序数组

33. 搜索旋转排序数组

地址:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

题目描述

整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., 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 。

示例

示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1

分析

由于是有序数组找指定数字 所以明显是用二分查找来解决
但是由于数组中存在反转,所以需要对二分的判定标准进行修改,判定左右是否有序
当target值大于nums[mid}时,普通的有序数组是去数组的右侧,即[mid+1,right]继续进行二分,
而反转有序数组 先判定右侧是否有序(nums[mid]<=nums[right]),当该区间有序且nums[right]>=target时 继续在该区间进行二分,若区间无序说明 左区间[left,mid-1]必有序,不可能存在target,因此继续在右侧区间二分 ,其余情况都去左侧区间查找

官方思路
在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分查找的上下界,因为我们能够根据有序的那部分判断出 target 在不在这个部分:

如果 [l, mid - 1] 是有序数组,且 target 的大小满足 [nums[l],nums[mid])[nums[l],nums[mid]),则我们应该将搜索范围缩小至 [l, mid - 1],否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组,且 target 的大小满足 (nums[mid+1],nums[r]](nums[mid+1],nums[r]],则我们应该将搜索范围缩小至 [mid + 1, r],否则在 [l, mid - 1] 中寻找。

leetcdoe 33. 搜索旋转排序数组

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right = nums.size()-1;
        int mid=0;
        while(right>=left)
        {
            mid =(left+right)/2;

            if(nums[mid]==target)
            {
                return mid;
            }else if(nums[mid]>target)
            {
                if(nums[left]<=nums[mid]  && nums[left]<=target ||nums[mid]<=nums[right])
                    right =mid -1;
                else
                    left =mid+1;
            }else{ 
                if(nums[mid]<nums[right] && nums[right]>= target || nums[left]<=nums[mid])
                {
                    left =mid+1;
                }else
                {
                    right =mid -1;
                }
            }
        }
        return -1;
    }
};

官方题解

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

leetcdoe 33. 搜索旋转排序数组

上一篇:python requests check_hostname requires server_hostname


下一篇:spring-boot 2.5.4,nacos 作为配置、服务发现中心,Cloud Native Buildpacks 打包镜像,GitLab CI/CD