Medium
服气的，至少三个多月没有碰过二分法果然稍微复杂点的就不会了,很多细节根本不懂为什么。这道题特别之处还在于能有duplicates, 导致worst case is O(n).
这个方法虽然也能做Search in Rotated Sorted Array I, 但是和我原来比较熟悉的先找最小element的方法比较不一样，让我有点不清楚，所以还是得会以前那种先找smallest element的方法, because it makes more sense to me. 然而尝试了一下，发现要考虑的情况太多了，暂时觉得消化不了.

Yes, when there could be duplicates in the array, the worst case is O(n).
To explain why, consider this sorted array 1111115, which is rotated to 1151111.
Assume left = 0 and mid = 3, and the target we want to search for is 5. Therefore, the condition A[left] == A[mid] holds true, which leaves us with only two possibilities:
All numbers between A[left] and A[right] are all 1's.
Different numbers (including our target) may exist between A[left] and A[right].
As we cannot determine which of the above is true, the best we can do is to move left one step to the right and repeat the process again. Therefore, we are able to construct a worst case input which runs in O(n), for example: the input 11111111...115.

discussion里面有人说了，有重复元素的时候最坏情况是O(N), 因为当nums[mid] == nums[start]的时候我们采用的是start++一步一步右移.

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return false;
        }  
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end){
            int mid = start + (end - start) / 2;
            if (nums[mid] == target){
                return true;
            } else if (nums[mid] < nums[start]){
                if (target <= nums[end] && target >= nums[mid]){
                    start = mid;
                } else {
                    end = mid;
                }
            } else if (nums[mid] > nums[start]){
                if (target >= nums[start] && target <= nums[mid]){
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                start++;
            }
        }
        if (nums[start] == target || nums[end] == target){
            return true;
        } 
        return false;
    }
}