Search in Rotated Sorted Array I & 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.
会有影响的，我们在没有dupliate的情况下，只要判断A[mid]和A[start]的大小就可以确定左边还是右边是递增序列，但是如果有duplicate的情况的时候，就判断不了了11131和13111比较结果是一样的，其实处理很简单，就是start++然后再比较就是了。

另外即使有duplicate，只要找到递增数列，然后带入下一个recursion就好了，recursion自然会一个一个把重复序列去除掉的。

public class Solution {
    public boolean search(int[] A, int target) {
        if (A.length == 0)
            return false;
        return binarySearch(A, target, 0, A.length - 1);
    }
    
    public boolean binarySearch(int [] A, int t, int start, int end)
    {
        if (start > end)
            return false;
        if (start == end)
            return (A[start] == t);
        int mid = (start + end)/2;
        if (A[mid] == t)
            return true;
        if (A[mid] > A[start]) //left side is acceding
        {
            if (t < A[mid] && t >= A[start]) // check for the complete ascending side
            {
                return binarySearch(A, t, start, mid-1);
            }
            else
            {
                return binarySearch(A, t, mid + 1, end);
            }
        }
        else if (A[mid] < A[start]) //right side accending
        {
            if (t > A[mid] && t <= A[end])
            {
                return binarySearch(A, t, mid + 1, end);
            }
            else
            {
                return binarySearch(A, t, start, mid - 1);
            }
        }
        else
        {
            start++;
            return binarySearch(A, t, start, end);
        }
    }
}

Simpler code for no duplicate (Search in Rotated Sorted Array I). consider the problem in two different conditions

public class Solution {
    public int search(int[] A, int target) {
        return rotatedBinarySearch(A, target, 0, A.length-1);
    }
    
    public int rotatedBinarySearch(int [] A, int target, int start, int end) {
        int mid = (start + end) / 2;
        if (start > end)
            return -1; 
        if (A[mid] == target) 
            return mid;
        if (A[mid] < A[start]) { // like 6701245
            if (target > A[mid] && target <= A[end])
                return rotatedBinarySearch(A, target, mid+1, end);
            else
                return rotatedBinarySearch(A, target, start, mid-1);
        }
        else { // like 2456701
            if (target < A[mid] && target >= A[start])
                return rotatedBinarySearch(A, target, start, mid-1);
            else
                return rotatedBinarySearch(A, target, mid+1, end);
        }
    }
}

Notice that if we find A[mid] == A[start] for duplicate, we can not be sure which way to go (left half or right half). The only way to diff is simply remove the first element and try to binary search again. This step of course in worst case will result in O(n) run time.

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

Advertisements