一、問題描述
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:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

二、解決思路
思路一：題目已明確了數(shù)組中不包含重復(fù)元素，并且時間復(fù)雜度必須是O(logn)，可以直接通過二分查找來判斷是否含有目標(biāo)元素，只是一些臨界條件需要注意
思路二：數(shù)組是一個有序數(shù)組旋轉(zhuǎn)后的結(jié)果，分為兩段有序，因此，可以先求出后段有序的起始下標(biāo)，然后在分治兩段進(jìn)行二分查找
思路三：參考了其他人的解決思路，先找出后段有序的起始下標(biāo) k，再根據(jù)真正二分查找算法找到二分?jǐn)?shù)組元素（下標(biāo)為 (mid + k) % n），直到找到是否存在該目標(biāo)元素，這種思路太巧妙了

三、算法實(shí)現(xiàn)
思路一：

public int search(int[] nums, int target) {
        int lens = nums.length - 1;
        int left = 0;
        int right = lens;
        while(left != right){
            int mid = (left + right) / 2;
            System.out.println(left + ", " + mid + ", " + right);
            if(nums[mid] == target) return mid;
            if(mid == left){
                if(nums[right] == target) return right;
                else break;
            }
            if(mid == right){
                if(nums[left] == target) return left;
                else break;
            }
            // 該范圍數(shù)組有序
            if(nums[right] > nums[left]){
                if(nums[mid] > target){
                    right = mid;
                } else {
                    left = mid;
                }
            } else { // 該范圍數(shù)組兩段有序
                if(nums[mid] > nums[left]){ // 處于前段內(nèi)
                    if(target >= nums[left] && target < nums[mid]){
                        right = mid;
                    } else {
                        left = mid;
                    }
                } else { // 處于后段內(nèi)
                    if(target > nums[mid] && target <= nums[right]){
                        left = mid;
                    } else {
                        right = mid;
                    }
                }
            }
        }
        return -1;
    }

思路二：

public int getCenterIdx(int[] nums){
        int lens = nums.length;
        if(nums[0] < nums[lens - 1]) return 0;
        int left = 0;
        int right = lens - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] > nums[left]) left = mid;
            else right = mid;
        }
        return left + 1;
    }

    public int search(int[] nums, int target){
        if(nums.length == 0) return -1;
        int lens = nums.length;
        int left = 0;
        int right = lens - 1;
        int idx = getCenterIdx(nums);
        //System.out.println("idx = " + idx);
        if(idx == 0) {
            if(nums[0] == target) return 0;
            return secondIndex(nums, left, right, target);
        } else {
            if(nums[left] <= target && nums[idx - 1] >= target){
                right = idx - 1;
                return secondIndex(nums, left, right, target);
            } else {
                left = idx;
                return secondIndex(nums, left, right, target);
            }
        }
    }

    public int secondIndex(int[] nums, int left, int right, int target){
        if(left < 0 || right > nums.length - 1 || right < left) return -1;
        if(nums[left] == target) return left;
        if(nums[right] == target) return right;
        if(target > nums[right]) return -1;
        if(target < nums[left]) return -1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return -1;
    }

思路三

public int getCenterIdx(int[] nums){
        int lens = nums.length;
        if(nums[0] < nums[lens - 1]) return 0;
        int left = 0;
        int right = lens - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] > nums[left]) left = mid;
            else right = mid;
        }
        return left + 1;
    }

public int search(int[] nums, int target){
        if(nums.length == 0) return -1;
        int lens = nums.length;
        int left = 0;
        int right = lens - 1;
        int idx = getCenterIdx(nums);
        while(left <= right){
            int mid = (left + right) / 2;
            int realIdx = (mid + idx) % lens;
            if(nums[realIdx] == target) return realIdx;
            else if(nums[realIdx] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }