摘要：如果左邊的點比右邊的大，說明這兩個點之間有一個旋轉點，導致了不再有序。因為只有一個旋轉點，所以一分為二后，肯定有一半是有序的。

Suppose a sorted array 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.

最新更新請見：https://yanjia.me/zh/2019/01/...

時間 O(logN) 空間 O(1)

平時我們二分法的時候，直接判斷下中點和目標的關系，就可以知道目標在左半部分還是右半部份了，這背后其實隱含一個假設，那就是從起點到終點是一段有序的序列。而本題中，如果我們還想繼續做二分法，這個假設就不存在了，因為從起點到終點有可能有個斷片！不過，旋轉有序數組有一個特點，假設本身是個升序序列，從左向右。如果左邊的點比右邊的點小，說明這兩個點之間是有序的，不存在旋轉點。如果左邊的點比右邊的大，說明這兩個點之間有一個旋轉點，導致了不再有序。因為只有一個旋轉點，所以一分為二后，肯定有一半是有序的。所以，我們還是可以用二分法，不過要先判斷左半邊有序還是右半邊有序。如果左半邊有序，則直接將目標和左半邊的邊界比較，就知道目標在不在左半邊了，如果不在左半邊肯定在右半邊。同理，如果右半邊有序，則直接將目標和右半邊的邊界比較，就知道目標在不在右半邊了，如果不在右半邊肯定在左半邊。這樣就完成了二分。

這里要注意二分時候的邊界條件，一般來說我們要找某個確定的目標時，邊界條件為：

min = 0, max = length - 1;
if(min <= max){
    min = mid + 1
    max = mid - 1
}

另外，判斷左半邊是否有序的條件是：nums[min] <= nums[mid]，而判斷是否在某一個有序區間，則要包含那個區間較遠的那一頭

迭代寫法

public class Solution {
    public int search(int[] nums, int target) {
        int min = 0, max = nums.length - 1, mid = 0;
        while(min <= max){
            mid = (min + max) / 2;
            if(nums[mid] == target){
                return mid;
            }
            // 如果左半部分是有序的
            if(nums[min] <= nums[mid]){
                if(nums[min] <= target && target < nums[mid]){
                    max = mid - 1;
                } else {
                    min = mid + 1;
                } 
            // 如果右半部份是有序的
            } else {
                if(nums[mid] < target && target <= nums[max]){
                    min = mid + 1; 
                } else {
                    max = mid - 1;
                }
            }
        }
        // 不滿足min <= max條件時，返回-1
        return -1;
    }
}

遞歸寫法

public class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, 0, nums.length - 1, target);
    }
    
    public int helper(int[] nums, int min, int max, int target){
        int mid = min + (max - min) / 2;
        // 不滿足min <= max條件時，返回-1
        if(min > max){
            return -1;
        }
        if(nums[mid] == target){
            return mid;
        }
        // 如果左半部分是有序的
        if(nums[min] <= nums[mid]){
            // 如果在左半部分的邊界內
            if(nums[min] <= target && target < nums[mid]){
                return helper(nums, min, mid - 1, target);
            // 如果不在左半部分的邊界內
            } else {
                return helper(nums, mid + 1, max, target);
            }
        // 如果右半部份是有序的
        } else {
            // 如果在右半部分的邊界內
            if(nums[mid] < target && target <= nums[max]){
                return helper(nums, mid + 1, max, target);
            // 如果不在右半部分的邊界內
            } else {
                return helper(nums, min, mid - 1, target);
            }
        }
    }
}

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

時間 O(N) 空間 O(1)

如果可能有重復，那我們之前判斷左右部分是否有序的方法就失效了，因為可能有這種13111情況，雖然起點小于等于中間，但不代表右邊就不是有序的，因為中點也小于等于終點，所有右邊也是有序的。所以，如果遇到這種中點和兩邊相同的情況，我們兩邊都要搜索。

public class Solution {
    public boolean search(int[] nums, int target) {
        return helper(nums, 0, nums.length - 1, target);
    }
    
    public boolean helper(int[] nums, int min, int max, int target){
        int mid = min + (max - min) / 2;
        // 不符合min <= max則返回假
        if(min > max){
            return false;
        }
        if(nums[mid] == target){
            return true;
        }
        boolean left = false, right = false;
        // 如果左邊是有序的
        if(nums[min] <= nums[mid]){
            // 看目標是否在左邊有序數列中
            if(nums[min] <= target && target < nums[mid]){
                left = helper(nums, min, mid - 1, target);
            } else {
                left = helper(nums, mid + 1, max, target);
            }
        }
        // 如果右邊也是有序的
        if(nums[mid] <= nums[max]){
            // 看目標是否在右邊有序數列中
            if(nums[mid] < target && target <= nums[max]){
                right = helper(nums, mid + 1, max, target);
            } else {
                right = helper(nums, min, mid - 1, target);
            }
        }
        // 左右兩邊有一個包含目標就返回真
        return left || right;
    }
}