思路

• 画图分析
• 先找到最小值(左右的分界点)
• 再根据target的范围(<=nums[n-1])来分段二分

时间复杂度(三段二分 O(logn))

注意事项：边界

/**
* 画图:先找到最小值，再根据范围二分
* 注意边界情况
*/
class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return -1;
        int n = nums.length;
        int l = 0;
        int r = n-1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums[n-1])
                r = mid;
            else
                l = mid+1;
        }
        int min = l;
        if(target <= nums[n-1]){
            l = min;
            r = n-1;
            while(l < r){
                int mid = l + r >> 1;
                if(nums[mid] >= target)
                    r = mid;
                else
                    l = mid + 1;
            }
            if(nums[r] == target)
                return r;
        }else{
            l = 0;
            r = min - 1;
            while(l < r){
                int mid = l + r >> 1;
                if(nums[mid] >= target)
                    r = mid;
                else
                    l = mid + 1;
            }
            if(nums[l] == target)
                return l;
        }
        return -1;
    }
}