Leetcode 81 - Search in Rotated Sorted Array II

http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-ii-java/

Follow up for "Search in Rotated Sorted Array": what if duplicates are allowed? Write a function to determine if a given target is in the array.

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

http://www.cnblogs.com/anne-vista/p/4899753.html

解题思路一致。只有重复数的差别。

当有重复数字，会存在A[mid] = A[end]的情况。此时右半序列A[mid-1 : end]可能是sorted，也可能并没有sorted，如下例子。

3 1 2 3 3 3 3 
3 3 3 3 1 2 3

所以当A[mid] = A[end] != target时，无法排除一半的序列，而只能排除掉A[end]：

A[mid] = A[end] != target时：搜寻A[start : end-1]

正因为这个变化，在最坏情况下，算法的复杂度退化成了O(n)：

序列 2 2 2 2 2 2 2 中寻找target = 1。

    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        int index = -1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target) {
                index = mid;
            }
            if(nums[mid] < nums[right]) { //right half sorted
                if(target > nums[mid] && target <= nums[right]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }else if(nums[mid] > nums[right]){ //left half sorted
                if(target >= nums[left] && target < nums[mid]){
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else{
                right--;
            }
        }
        return index != -1;
    }

http://codesniper.blogspot.com/2015/03/81-search-in-rotated-sorted-array-ii.html