康瑞部落

Search in Rotated Sorted Array II

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.

解题思路：

同Search in Rotated Sorted Array一样，这道题也可以用二分查找。不同的是，这道题元素可以相同，因此，在最坏的情况下时间复杂度为O(n)。

在每次二分查找之前，先压缩左右区间。然后判断：

1、当nums[left]、nums[middle]、nums[right]之一与target相同时，返回true

2、当target<nums[middle]时，分middle在大部还是小部两种情况：

（1）若middle在大部，即nums[middle] > nums[left]，则看nums[left]的大小。若nums[left]>target，那么left~middle可以排除，让left=middle+1。若nums[left]<target,那么target的值只能存在left~middle之间，让right=middle - 1

（2）若middle在小部，即nums[middle] < nums[left]，那么middle~right可以排除，令right = middle - 1

3、同样，当target>nums[middle]时，分middle在大部还是小部两种情况：

（1）若middle在大部，即nums[middle]>nums[left]，那么left~middle可以排除，令left=middle + 1

（2）若middle在小部，即nums[middle]<nums[left]。如果nums[right]>target，那么target可定在middle~right之间，令left=middle+1。否则，nums[right]<target，那么可以排除middle~right之间的元素，令right = middle - 1

下面是代码：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right){
            while(left < right && left<len - 1 && nums[left] == nums[left+1]){
                left++;
            }
            while(left < right && right>=1 && nums[right] == nums[right-1]){
                right--;
            }
            int middle = (left + right) / 2;
            if(target == nums[middle] || target == nums[left] || target == nums[right]){
                return true;
            }else if(target < nums[middle]){
                if(nums[middle]>nums[left]){   //表明middle在大部
                    if(nums[left] > target){
                        left = middle + 1;
                    }else{
                        right = middle - 1;
                    }
                }else{                          //表明middle在小部
                    right = middle - 1;
                }
            }else{
                if(nums[middle]>nums[left]){   //表明middle在大部
                    left = middle + 1;
                }else{                          //表明middle在小部
                    if(nums[right]>target){
                        left = middle + 1;
                    }else{
                        right = middle - 1;
                    }
                }
            }
        }
        return false;
    }
};