Search in Rotated Sorted Array II 63

Question

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.

Example

Given [1, 1, 0, 1, 1, 1] and target = 0, return true.

Given [1, 1, 1, 1, 1, 1] and target = 0, return false.

Solution

这道题是有重复元素的情况下对rotated sorted array进行搜索。

一种做法是进行顺序搜索，这样复杂度是O(n)。

另一种做法是进行二分搜索，但是因为有重复元素（特别是重复元素有可能被分在前后区间），此时对于nums[mid] == nums[left]情况不能像之前那样合并在nums[left] < nums[mid]或者nums[left] > nums[mid]之中进行讨论，必须进行单独讨论，因为nums[mid] == nums[left]有可能是因为mid==left，但也有可能是因为nums[mid]和nums[left]是重复元素，如果是后面这种情况则mid有可能其实是落在后半区，这时能确定的只是nums[left]一定不等于target，其他情况都是不确定的，因此最保险的方法是只将left向右移动一步，即left++。这种情况下，如果数组大部分是重复元素，则复杂度接近O(n)，但是如果重复元素较少，则时间复杂度接近O(logn)。

代码如下：

public class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
    public boolean search(int[] A, int target) {
        // write your code here
        int[] nums = A;
        if(nums == null || nums.length == 0){
            return false;
        }

        int left = 0;
        int right = nums.length - 1;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return true;
            }else if(nums[left] < nums[mid]){
                if(nums[left] <= target && target <= nums[mid]){
                    right = mid;
                }else{
                    left = mid;
                }
            }else if(nums[left] > nums[mid]){
                if(nums[mid] <= target && target <= nums[right]){
                    left = mid;
                }else{
                    right = mid;
                }
            }else if(nums[left] == nums[mid]){
            //这里是关键，如果有重复元素，只将left向right移动一位，肯定不会有问题
                left++;
            }
        }

        if(nums[left] == target){
            return true;
        }else if(nums[right] == target){
            return true;
        }
        return false;
    }
}