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

数组旋转之后，应该是从开始数值上升，上升到旋转数组之前的最小值时，数值drop，然后继续上升 在用二分法时应该先判断mid 到底是在第一个上升区间，还是第二个上升区间 判断好了在哪个上升区间以后，再判断target在mid的哪个部分，这里有Cornercase， 如果在第一个上升区间里时，nums[mid] > target，直接将end = mid,那么 target 有可能在第二个上升区间，这样就会错过。 所以正确的排查顺序 应该是，在第一个上升区间时，先判断target是不是在[start, mid]之间，因为这样不会错过，在第二个上升区间时，从后往前判断，target是不是在[mid, end]之间，要主要，判断start mid end 所在值是否也等于target，像常规判断二分那样

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            
            if(nums[mid] == target)
                return mid;
            
            //判断mid落在哪一个区间
            if(nums[mid] > nums[start]){
                //然后按照常规二分法来寻找target
                if(target >= nums[start] && target <= nums[mid]){
                    end = mid;
                }else{
                    start = mid;
                }
               
            }
            else{
                if(target <= nums[end] && target >= nums[mid]){
                    start = mid;
                }
                else{
                    end = mid;
                }
            }
            
        }
        
        if(nums[start] == target){
            return start;
        }
        if(nums[end] == target)
            return end;
        
        return -1;
    }
}