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.

Answer 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.