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 。

分析

以数组[0,1,2,4,5,6,7]为例，当其在下标3处经旋转后变为[4,5,6,7,0,1,2]，如果我们要找的数target为0，怎么快速找到他呢？ 可以通过二分查找快速定位到该数存在的区间，逐渐缩小其可能存在的区间范围从而定位到元素。
若数组为[4,5,6,7,0,1,2]，第一次进入此时left=0，right=7;不难看出mid=3;nums[mid]的位置对应的就是数字7，那么该数组就变成了两个区间[4,5,6,7]和[0,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-left)>>1);
            if(nums[left]<=nums[mid]){
                if(nums[left]<=target&&target<=nums[mid]){
                    if(nums[mid]==target) return mid;
                    if(nums[left]==target) return left;
                    else right = mid;
                }else{
                    left=mid+1;
                }
            }else{
                if(nums[mid]<target&&target<=nums[right]){
                    if(nums[right]==target) return right;
                    else left = mid+1;
                }else{
                    right = mid;
                }
            }
        }
        return nums[left]==target?left:-1;
    }
}

说明

将数组分为几个区间进行取值判断

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

确认[left,mid]是一段上升区间，他的最大值和最小值是确定的，
所以当nums[left]<=target&&target<=nums[mid]判断出true说明target一定在这个区间里的，我们只需要不断的缩小右区间让target落在left或者mid上即可，但是如果target不在这个区间里，我们就需要让我们搜索的范围跳出这个区间即left=mid+1。那另外一段代码就很好理解了

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

如果不在[left,mid]这个区间那么target只可能出现在(mid,right]这个区间里，通过nums[mid]<target&&target<=nums[right]来确定target是否在这个区间,如果不在这个区间，那么右区间向左收缩，如果在，那么左区间向右搜索。
最后，因为我们是通过排除区间的方法来查询的，最后剩下来的区间只是可能存在目标值，还得通过一层判断

nums[left]==target?left:-1;

来返回最后的结果信息。