CodeTop day4

class Solution {
    public int search(int[] nums, int target) {
        //大体是两种情况，但其实是三种情况
        //第一种：包含target的元素被旋转了
        //1.1：target被旋转到前面部分
        //1.2：target被旋转了，但是位置没有发送改变
        //第二钟，包含target的元素没有被旋转

        //找到最小元素，即可以分成被旋转部分和未旋转部分
        int min = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i=0;i<nums.length;i++){
            if (nums[i]<min){
                minIndex = i;
                min = nums[i];
            }
        }
        if (nums[0]>target ){
            return binarySearch(nums,minIndex,nums.length,target);
        }else if(nums[0]<=target){
            //旋转了
            if (minIndex!=0){
                return binarySearch(nums,0,minIndex,target);
            }else{
                //旋转之后数组没有变化
                return binarySearch(nums,0,nums.length,target);
            }
        }
        return -1;
    }
    private int binarySearch(int[] nums, int start, int end, int target){
        int left = start;
        int right = end;
        while(left<right){
            int mid = (right+left)>>1;
            if (nums[mid]==target) return mid;
            if (nums[mid]>target){
                right = mid;
            }else{
                left = mid + 1;
            }
        } 
        return -1;
    }
}