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.