leetcode 33. Search in Rotated Sorted Array

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

思路1：分析mid所在区间的情况

nums[mid]要么落在左边升序的数据区间内，要么落在右边升序的数据区间内。

• 当nums[mid]在右边升序区间内，若nums[mid]<target<nums[right],向右查找；否则向左查找。
• 当nums[mid]在左边升序区间内，若nums[left]<=target<nums[mid],向左查找；否则向右查找。

第一种情况：(nums[mid]>nums[left]) nums[mid]落在了左边升序区间

此时若target>nums[mid],则查找的数在mid和right之间，left=mid+1

若target<nums[mid]，则查找的数可能在最左边的[left,mid]之间，也可能在最右边的[mid+1,right]之间。

此时需要将target和nums[left]进行比较，来确定target在哪个子区间。

第二种情况：nums[mid]<nums[left]，mid落在了右边升序区间。

此时如果target<nums[mid],则target在右边区域靠左部分，right=mid-1

若target>nums[mid]，则此时target可能存在于右边区域的靠右部分，[mid+1,right]，也可能存在于左边区域[left,mid]中

此时需要将nums[mid]与nums[right]进行比较，确定具体属于哪个子区间。

实现1：

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==1&&nums[0]==target) return 0;
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[left]==target) return left;
            if(nums[right]==target) return right;
            if(nums[mid]==target) return mid;
            if(nums[mid]>nums[left]){
                if(target>nums[mid]){
                    left=mid+1;
                }else{
                    if(target>nums[left]){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                }
            }else{
                if(target<nums[mid]){
                    right=mid-1;
                }else{
                    if(target<nums[right]){
                        left=mid+1;
                    }else{
                        right=mid-1;
                    }
                }
            }
        }
        return -1;
    }
}

实现2：

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<nums[right]){
                //落在了右边区域
                if(nums[mid]<target&&target<=nums[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }              
            }else{
                if(nums[left]<=target&&target<nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
                
            }
        }
        return -1;
    }
}

思路2：先利用二分查找确定转折点，然后对转折点两侧的数据分别再进行二分查找。

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==0) return -1;
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(nums[mid]>nums[right]){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        //找到了旋转点
        int a=binarySearch(nums,target,0,right-1);
        int b=binarySearch(nums,target,right,nums.length-1);
        return a>b?a:b; 
    }
    private int binarySearch(int[] nums,int target,int left,int right){
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return -1;
    }
}

参考：

https://blog.****.net/m0_37874657/article/details/80024188

https://blog.****.net/seniusen/article/details/83447729