1、前言

2、思路

本题的思路是使用二分查找，要分清楚数组的前半部分有序还是后半部分有序。
1 2 3 4 5 6 7 可以大致分为两类，
第一类 2 3 4 5 6 7 1 这种，也就是 nums[start] <= nums[mid]。此例子中就是 2 <= 5。
这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找。
第二类 6 7 1 2 3 4 5 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2。
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]，则在后半部分找，否则去前半部分找。

3、代码

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }

        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;

            if(nums[mid] == target){
                return mid;
            }

            // mid 落在左边，但只有 [left, mid] 能确定，其他情况要继续判断
            if(nums[mid] >= nums[left]){
                if(nums[left] <= target && target <= nums[mid]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }else if(nums[mid] < nums[left]){ // mid 落在右边，但只有 [mid, right] 能去定，其他情况要继续判断
                if(nums[mid] <= target && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}