Medium
服氣的番宁，至少三個多月沒有碰過二分法果然稍微復(fù)雜點的就不會了,很多細節(jié)根本不懂為什么射窒。這道題特別之處還在于能有duplicates, 導(dǎo)致worst case is O(n).
這個方法雖然也能做Search in Rotated Sorted Array I, 但是和我原來比較熟悉的先找最小element的方法比較不一樣恃疯，讓我有點不清楚，所以還是得會以前那種先找smallest element的方法, because it makes more sense to me. 然而嘗試了一下码俩，發(fā)現(xiàn)要考慮的情況太多了纵东，暫時覺得消化不了.

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里面有人說了，有重復(fù)元素的時候最壞情況是O(N), 因為當(dāng)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;
    }
}