二分查找4 - 搜索旋转排序数组

搜索旋转数组

1. 题目
整数数组 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 。

来源：力扣（LeetCode）
二 解法一
思路：既然数组在某个位置k做了扭转，则说明nums[0,k]与nums[k+1,nums.length-1]这两个数组都是有序的。我们可以先遍历数组，找出K位置，然后根据target情况选定一个区间来做二分查找。

class Solution {
    
    public int search(int[] nums, int target) {
    
        int index = -1,left=0,right= nums.length-1;
        int reverse = -1;
        if(nums.length>1){
    
            for(int i=0;i< nums.length-1;i++){
    
                if(nums[i]>nums[i+1]){
    
                    reverse = i+1;
                    break;
                }
            }
            if(reverse>0){
    
                if(target>=nums[reverse]&&target<=nums[nums.length-1]){
    
                    left = reverse;
                    right = nums.length-1;
                    index = getResult(left,right,nums,target);
                }else if(target>=nums[0]&&target<=nums[reverse-1]){
    
                    left = 0;
                    right = reverse-1;
                    index = getResult(left,right,nums,target);
                }
            }else{
    
                index = getResult(left,right,nums,target);
            }
        }else if(nums.length==1&&nums[0]==target){
    
            index = 0;
        }
        return index;
    }
    private int getResult(int left,int right,int[] nums, int target){
    
        int index = -1,mid,l=left,r=right;
        while(l<=r){
    
            mid = l+(r-l)/2;
            if(nums[mid]==target){
    
                index = mid;
                break;
            }else if(nums[mid]<target){
    
                l=mid+1;
            }else{
    
                r=mid-1;
            }
        }
        return index;
    }
}

三 解法二
因为数组只在一处做了扭转，因此将数组从mid分为两部分，总有一部分是有序的，一部分是无序的。对于有序的部分，若target属于有序的区间，则在有序区间使用二分查找求值。若不属于有序区间，则在无序区间中，继续使用新的mid，将无序区间分为两半，重复上面过程。

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