Seaching 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). ex: 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, thanks Moron for letting me know.

Answer 1

You can use binary search to find the location of smallest element and reduce it to O(Log n).

You can find the location by (this is just a sketch of algorithm, it's inaccurate but you can get the idea from it):
1. i <- 1
2. j <- n
3. while i < j
3.1. k <- (j-i) / 2
3.2. if arr[k] < arr[i] then j <- k 3.3. else i <- k

After finding the location of the smallest element you can treat the array as two sorted arrays.

Answer 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)!

Answer 3

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.

Answer 4

You just use a simple binary search as if it were a regular sorted array. The only trick is you need to rotate the array indexes:

(index + start-index) mod array-size

where the start-index is the offset of the first element in the circular array.

Answer 5

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.

Answer 6

guirgis: It is lame to post an interview question, guess you didn't get the job :-(

Use a special cmp function and you need only one pass with regular binary search. Something like:

def rotatedcmp(x, y):
  if x and y < a[0]:
    return cmp(x, y)
  elif x and y >= a[0]:
    return cmp(x, y)
  elif x < a[0]:
    return x is greater
  else:
    return y is greater

If you can depend on int underflow subtract a[0] - MIN_INT from each element as it is accessed and use regular compare.