27

17

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.

You should clarify whether or not you know in advance where the circular array begins. Typically in real-world applications you would know. – Christopher Barber – 2010-05-14T14:26:16.343

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. – guirgis – 2010-05-14T14:38:22.197

You need to know if elements are distinct. Otherwise worst case is Omega(n). – None – 2010-05-14T17:15:13.557

2

See also http://stackoverflow.com/questions/2796413/binary-search-to-find-the-rotation-point-in-a-rotated-sorted-list

– starblue – 2010-05-15T06:30:17.203Given 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 https://stackoverflow.com/a/7694019/2812818

– Droid Teahouse – 2017-12-23T01:29:47.433