leetcode 33. 搜索旋转排序数组

一、题目

整数数组 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 。

二、解法

思路：二分查找
在数组的 left 和 right 之间查找。刚开始是 [0,length-1]范围。当 right-left+1==0 是停止查找（长度为1）。

mid=left+(right-left)/2 ，分成两部分 [left,mid] 和 [mid+1,right] ，问题在于要选择哪一部分。由于数组是旋转的升序数组，分成两部分后，必然有一部分是升序的，另一部分可能是升序，也有可能是两段升序拼起来的。那么对于其中升序的数组，进行判断是否在其中，如果不在，就去另一部分中查找。

class Solution {
    public int binarySearch(int[] nums,int target,int left,int right){
        int len=right-left+1;
        if(len==1){
            if(nums[left]==target) return left;
            else return -1;
        }else{
            int mid=left+(right-left)/2;
            if(nums[left]<=nums[mid]){  //左边是升序
                if(target>=nums[left]&&target<=nums[mid]){
                    return binarySearch(nums,target,left,mid);
                }else{
                    return binarySearch(nums,target,mid+1,right);
                }
            }else{  //右边是升序
                if(target>=nums[mid+1]&&target<=nums[right]){
                    return binarySearch(nums,target,mid+1,right);
                }else{
                    return binarySearch(nums,target,left,mid);
                }
            }
        }
    }
    public int search(int[] nums, int target) {
        int len=nums.length;
        return binarySearch(nums,target,0,len-1);
    }
}

leetcode 33. 搜索旋转排序数组

原文：https://www.cnblogs.com/livingsu/p/14932440.html