Searching for an element in a circular sorted array

Question

We want to search for a given element in a circular sorted array in complexity not greater than O(log n).
Example: Search for 13 in {5,9,13,1,3}.

My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm I came up was stupid that it takes O(n) in the worst case:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

then the corresponding index of ith element will be determined from the following relation:

(i + minInex - 1) % a.length

it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one.

According to ire_and_curses idea, here is the solution in Java:

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1;
    if(a[mid] == x){
        return mid;
    }
    //a variable to indicate which half is sorted
    //1 for left, 2 for right
    int sortedHalf = 0;
    if(a[low] <= a[mid]){
        //the left half is sorted
        sortedHalf = 1;
        if(x <= a[mid] && x >= a[low]){
            //the element is in this half
            return binarySearch(a, low, mid, x);
        }
    }
    if(a[mid] <= a[high]){
        //the right half is sorted
        sortedHalf = 2;
        if(x >= a[mid] && x<= a[high] ){
            return binarySearch(a, mid, high, x);
        }
    }
    // repeat the process on the unsorted half
    if(sortedHalf == 1){
        //left is sorted, repeat the process on the right one
        return circularArraySearch(a, mid, high, x);
    }else{
        //right is sorted, repeat the process on the left
        return circularArraySearch(a, low, mid, x);
    }
}

Hopefully this will work.

Solution 1

You can do this by taking advantage of the fact that the array is sorted, except for the special case of the pivot value and one of its neighbours.

• Find the middle value of the array a.
• If a[0] < a[mid], then all values in the first half of the array are sorted.
• If a[mid] < a[last], then all values in the second half of the array are sorted.
• Take the sorted half, and check whether your value lies within it (compare to the maximum idx in that half).
• If so, just binary search that half.
• If it doesn't, it must be in the unsorted half. Take that half and repeat this process, determining which half of that half is sorted, etc.

Solution 2

Not very elegant, but of the top off my head - just use binary search to find the pivot of the rotated array, and then perform binary search again, compensating for the offset of the pivot. Kind of silly to perform two full searches, but it does fulfill the condition, since O(log n) + O(log n) == O(log n). Keep it simple and stupid(tm)!

Solution 3

This is an example that works in Java. Since this is a sorted array you take advantage of this and run a Binary Search, however it needs to be slightly modified to cater for the position of the pivot.

The method looks like this:

private static int circularBinSearch ( int key, int low, int high )
{
    if (low > high)
    {
        return -1; // not found
    }

    int mid = (low + high) / 2;
    steps++;

    if (A[mid] == key)
    {
        return mid;
    }
    else if (key < A[mid])
    {
        return ((A[low] <= A[mid]) && (A[low] > key)) ?
               circularBinSearch(key, mid + 1, high) :
               circularBinSearch(key, low, mid - 1);
    }
    else // key > A[mid]
    {
        return ((A[mid] <= A[high]) && (key > A[high])) ?
               circularBinSearch(key, low, mid - 1) :
               circularBinSearch(key, mid + 1, high);
    }
}

Now to ease any worries, here's a nice little class that verifies the algorithm:

public class CircularSortedArray
{
    public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 
                                   91, 99, 1, 4, 11, 14, 15, 17, 19};
    static int steps;

    // ---- Private methods ------------------------------------------

    private static int circularBinSearch ( int key, int low, int high )
    {
        ... copy from above ...
    }

    private static void find ( int key )
    {
        steps = 0;
        int index = circularBinSearch(key, 0, A.length-1);
        System.out.printf("key %4d found at index %2d in %d steps\n",
                          key, index, steps);
    }

    // ---- Static main -----------------------------------------------

    public static void main ( String[] args )
    {
        System.out.println("A = " + Arrays.toString(A));
        find(44);   // should not be found
        find(230);
        find(-123);

        for (int key: A)  // should be found at pos 0..18
        {
            find(key);
        }
    }
}

That give you an output of:

A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key   44 found at index -1 in 4 steps
key  230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key   23 found at index  0 in 4 steps
key   27 found at index  1 in 3 steps
key   29 found at index  2 in 4 steps
key   31 found at index  3 in 5 steps
key   37 found at index  4 in 2 steps
key   43 found at index  5 in 4 steps
key   49 found at index  6 in 3 steps
key   56 found at index  7 in 4 steps
key   64 found at index  8 in 5 steps
key   78 found at index  9 in 1 steps
key   91 found at index 10 in 4 steps
key   99 found at index 11 in 3 steps
key    1 found at index 12 in 4 steps
key    4 found at index 13 in 5 steps
key   11 found at index 14 in 2 steps
key   14 found at index 15 in 4 steps
key   15 found at index 16 in 3 steps
key   17 found at index 17 in 4 steps
key   19 found at index 18 in 5 steps

Solution 4

You have three values, l,m,h for the values at the low, mid and high indexes of your search. If you think were you would continue searching for each possibility:

// normal binary search
l < t < m    - search(t,l,m)
m < t < h    - search(t,m,h)

// search over a boundary
l > m, t < m - search(t,l,m)
l > m, t > l - search(t,l,m)
m > h, t > m - search(t,m,h)  
m > h, t < h - search(t,m,h)  

It's a question of considering where the target value could be, and searching that half of the space. At most one half of the space will have the wrap-over in it, and it is easy to determine whether or not the target value is in that half or the other.

It's sort of a meta question - do you think of binary search it terms of how it is often presented - finding a value between two points, or more generally as a repeated division of an abstract search space.

View more solutions

Comments

[Christopher Barber]

You should clarify whether or not you know in advance where the circular array begins. Typically in real-world applications you would know.

[guirgis]

No, i don't know where the cirular array begins, if i know then i won't need a conversion algorithm instead i'll apply the above relation directly and do a binary-search.

[Admin]

You need to know if elements are distinct. Otherwise worst case is Omega(n).

[starblue]

See also stackoverflow.com/questions/2796413/…

[Droid Teahouse]

Given the question constraints, it does not ever say the array is sorted, nor does it give any suggestion that it is partially sorted. Converting the array with sorting would knock you down to n time at best(counting sort with extra space complexity) and for most cases nlgn time. The array might be completely unsorted, making the binary search scheme unusable ( for lgn time.) see stackoverflow.com/a/7694019/2812818

[Frank]

That doesn't work. Your four cases come down to two (t<m and t>m) which do exactly the same as in normal binary search.

[Unreason]

+1: simple is good. it would probably be possible to do both at the same time; looking for wrapping point need to test if the order values for the current low and high indexes is reversed, if it is not then you are on the segment with no wrapping point and if(!) the sought value is in this segment then regular binary search can take care of it; if the number is not inside this segment or the segment has a wrapping point in it the split it and repeat; this way you either find the wrapping point or you reduce it to a regular binary search without finding it.

[ire_and_curses]

@Unreason - you just described the algorithm in my answer. ;)

[PeterAllenWebb]

I think the problem with this is that you don't know the position of the smallest value in the array in advance, which is what you are calling start index. It would be fairly simple to find that value in log(n) time, though: Just check the first last and middle values in the array. If first is larger than middle, you know the jump is between them. And you can use the same trick on that half of the array to find it. If middle is larger than second, it is in the second half. If neither of these is true, then the zero position of the array (or current sub array) is the start-position.

[Eyal Schneider]

+1 Nice. I believe this is the answer the interviewers were looking for. It uses the fact that in any segment of the array, at least one half is sorted, so we can use it to decide which half to continue with, thus reducing the search space by 2 in each step, as required.

[Admin]

Need distinct elements, else algorithm fails. And strangely, we can give a proof based on asymptotic runtime!

[Pete Kirkham]

Corrected the copy-paste error. Serves me right for being specific - a more descriptive version of the same thing got accepted.