public class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int len = nums.length;
        int high = len - 1;
        
        if(nums == null || len == 0)
            return -1;
            
        // find the biggest num index:  low
        while(low < high) {
            int median = (low + high) / 2;
            
            if(nums[median] > nums[low]) 
                low = median;
            else if(nums[median] < nums[low]){
                high = median - 1;
            } else {
                // median = low
                if(nums[low] <nums[high])
                    low = high;
                break;
            }
        }
        
        int index = binarySearch(nums, target, 0, low);
        if(index != -1)
            return index;
        
        index = binarySearch(nums, target, low + 1, len - 1);
        if(index != -1)
            return index;
        
        return -1;
    }

    private  int binarySearch(int[] nums, int target, int low, int high) {
        // 二分
        int median = (high+low) / 2;
        while(low <= high) {
            
            if(nums[median] == target) 
                return median;
            
            if(nums[median] > target) {
                high = median - 1;
            }
            else {
                low = median + 1;
            }
            median = low + (high-low) / 2;
        }
        return -1;
    }
}