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

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

        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int middle = start + (end - start) / 2;
            if(target >= nums[0]) {
                if(nums[middle] > target) end = middle;
                else if(nums[middle] < target) {
                    if(nums[middle] > nums[0]) start = middle;
                    else if(nums[middle] < nums[0]) end = middle;
                }else if(nums[middle] == target) return middle;
            }else if(target < nums[0]) {
                if(nums[middle] < target) start = middle;
                else if(nums[middle] > target) {
                    if(nums[middle] > nums[0]) start = middle;
                    else if(nums[middle] < nums[0]) end = middle;
                }else if(nums[middle] == target) return middle;
            }
        }

        if(nums[start] == target) return start;
        else if(nums[end] == target) return end;
        return -1;
    }
}


若数字有重复，那最坏情况是全部1，然后有一个0，target的值为0时，时间复杂度必然是o（n）。就写个普通的for循环好了