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).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

一刷
題解：
與第33題不同，第33題強調(diào)沒有duplicate, 重點還要分析時間復雜度。
當left part 不是升序，右邊也不是（相等），退化為順序搜索。

public class Solution {
    public boolean search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return false;
        return search(nums, target, 0, nums.length-1);
    }
    
    private boolean search(int[] nums, int target, int lo, int hi){
        while(lo<=hi){
            int mid = lo + (hi - lo)/2;
            if(nums[mid] == target) return true;
            if(nums[lo] < nums[mid]){//left part is sorted
                if(nums[lo] <= target && nums[mid] > target)
                    hi = mid - 1;
                else lo = mid + 1;
            }
            else if(nums[mid] < nums[lo]){//right part is sorted
                 if(nums[mid] < target && nums[hi] >= target)
                    lo = mid + 1;
                 else hi = mid - 1;
            }
            else lo++;
        }
        return false;
    }
}

二刷
思路，代碼同上。注意，當nums[lo] == nums[mid]，只能排除掉lo這個點。
比如[1,3,1,1,1], lo = 0, mid = 2.