LeetCode Search in Rotated Sorted Array II: More General & Compact Code

Overview

Whether or not duplicates exist in the rotated sorted array in this LeetCode problem can be handled consistently in a single copy of code with O(N) time bound.

That is, one can actually come up with a more general code to handle this LeetCode Rotated Sorted Array problem no matter duplicates exist or not consistently. The code run in O(logN) when no duplicates exists, while run in O(N) in the worst case when there are duplicates. I will analysis the reasons too.

Problem Definition

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.

Solution and Analysis

If there are duplicates in the array, then the worst search time has to be linear time. The thing is that when duplicates exists, we cannot easily determine which half is the increasing interval, say 2 2 2 2 2 2 2 2 2 3 2 2, for this case, we cannot tell which half is increasing by just observing the i, mid, j elements. The result is that to correctly determine if the target exists or not, we need to search through both half. Then it becomes actually a linear search.

However, one could still write the same copy of code to give a log(N) bound when there is no duplicates while it becomes O(N) when duplicates appear. The key point is that we can determine the rotated half instead of the increasing half any ways. Now we need to compare Array[i] with Array[mid], we also need to compare Array[mid] with Array[j], if there is no duplicates, then the rotated half must have the the first element is larger than the last element. Then we get to know the other half is the increasing half. Ok, things become the same as in no duplicates case. But if we cannot determine this, like in case 2 2 2 2 2 2 2 2 2 3 2 2, we have to search both half, and it becomes linear search.

Update: The way to determine if a linear scan needs to be adopted is to test if(Array[i] == Array[mid] && Array[j] == Array[mid]), if so, then we directly go to use linear scan, if not, we follow the binary search scheme.

Source Code Pass Both the Two Problem Tests

The following same source code is accepted by the LeetCode Oj for the Search in Rotated Sorted Array, both I and II, with or without duplicates:

int search(int A[], int n, int target) {
    int lo = 0, hi = n - 1;
    int mid = 0;

    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (A[mid] == target) 
            return mid;

        if (A[mid] < A[hi] && target <= A[hi] && target > A[mid])
            lo = mid + 1; 
        else if (A[mid] > A[lo] && target < A[mid] && target >= A[lo])
            hi = mid - 1; 
        else if (A[mid] < A[hi])  
            hi = mid - 1; 
        else if (A[mid] > A[lo])
            lo = mid + 1;
        else {
            if (A[mid] == A[lo])++lo;
            if (A[mid] == A[hi])--hi;
        }
    }
    return -1;
}

Summary

A consistent and compact code is given to solve LeetCode Search in Rotated Sorted Array problem Whether or not duplicates exist in O(N) time. Actually, this piece of code run in O(logN) when no duplicates exist and only run in O(N) when duplicates exist. This fact about the code is quite pleasing.

Written on May 16, 2013