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.

一刷
题解：
Binary Search
先判断是两个sorted array, 是左边的较长还是右边的较长。然后判断是在左半边还是在右半边

public class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return -1;
       return  search(nums, target, 0, nums.length-1);
    }
    
    public int search(int[] nums, int target, int start, int end){
        if(start>end) return -1;//not found
        int mid = start + (end-start)/2;
        if(nums[mid] == target) return mid;
        if(nums[start] < nums[mid]) //left is sorted
        {
            if(nums[start] <= target && nums[mid] > target)
                return search(nums, target, start, mid-1);
            else  return search(nums, target, mid+1, end);
        }
        else if(nums[start] > nums[mid]){//right is sorted
           if(nums[mid] < target && nums[end] >= target)
             return search(nums, target, mid+1, end);
            else return search(nums, target, start, mid-1);
        }
        else return search(nums, target, mid+1, end);
    }
}

二刷
思路同上

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