Searching for an element in a circular sorted array
https://stackoverflow.com/questions/2834652
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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
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.
OTHER TIPS
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)!
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
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.
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.
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.
public static int _search(int[] buff, int query){
int s = 0;
int e = buff.length;
int m = 0;
while(e-s>1){
m = (s+e)/2;
if(buff[offset(m)] == query){
return offset(m);
} else if(query < buff[offset(m)]){
e = m;
} else{
s = m;
}
}
if(buff[offset(end)]==query) return end;
if(buff[offset(start)]==query) return start;
return -1;
}
public static int offset(int j){
return (dip+j) % N;
}
Check this coe,
def findkey():
key = 3
A=[10,11,12,13,14,1,2,3]
l=0
h=len(A)-1
while True:
mid = l + (h-l)/2
if A[mid] == key:
return mid
if A[l] == key:
return l
if A[h] == key:
return h
if A[l] < A[mid]:
if key < A[mid] and key > A[l]:
h = mid - 1
else:
l = mid + 1
elif A[mid] < A[h]:
if key > A[mid] and key < A[h]:
l = mid + 1
else:
h = mid - 1
if __name__ == '__main__':
print findkey()
Here is an idea, related to binary search. Just keep backing up your index for the right array-index bound, the left index bound is stored in the step size:
step = n
pos = n
while( step > 0 ):
test_idx = pos - step #back up your current position
if arr[test_idx-1] < arr[pos-1]:
pos = test_idx
if (pos == 1) break
step /= 2 #floor integer division
return arr[pos]
To avoid the (pos==1) thing, we could back up circularly (go into negative numbers) and take (pos-1) mod n.
I think you can find the offset using this code:
public static int findOffset(int [] arr){
return findOffset(arr,0,arr.length-1);
}
private static int findOffset(int[] arr, int start, int end) {
if(arr[start]<arr[end]){
return -1;
}
if(end-start==1){
return end;
}
int mid = start + ((end-start)/2);
if(arr[mid]<arr[start]){
return findOffset(arr,start,mid);
}else return findOffset(arr,mid,end);
}
Below is a implementation in C using binary search.
int rotated_sorted_array_search(int arr[], int low, int high, int target)
{
while(low<=high)
{
int mid = (low+high)/2;
if(target == arr[mid])
return mid;
if(arr[low] <= arr[mid])
{
if(arr[low]<=target && target < arr[mid])
{
high = mid-1;
}
else
low = mid+1;
}
else
{
if(arr[mid]< target && target <=arr[high])
{
low = mid+1;
}
else
high = mid-1;
}
}
return -1;
}
Here's a solution in javascript. Tested it with a few different arrays and it seems to work. It basically uses the same method described by ire_and_curses:
function search(array, query, left, right) {
if (left > right) {
return -1;
}
var midpoint = Math.floor((left + right) / 2);
var val = array[midpoint];
if(val == query) {
return midpoint;
}
// Look in left half if it is sorted and value is in that
// range, or if right side is sorted and it isn't in that range.
if((array[left] < array[midpoint] && query >= array[left] && query <= array[midpoint])
|| (array[midpoint] < array[right]
&& !(query >= array[midpoint] && query <= array[right]))) {
return search(array, query, left, midpoint - 1);
} else {
return search(array, query, midpoint + 1, right);
}
}
Simple binary search with a little change.
Index of rotating array= (i+pivot)%size
pivot is the index i+1 where a[i]>a[i+1].
#include <stdio.h>
#define size 5
#define k 3
#define value 13
int binary_search(int l,int h,int arr[]){
int mid=(l+h)/2;
if(arr[(mid+k)%size]==value)
return (mid+k)%size;
if(arr[(mid+k)%size]<value)
binary_search(mid+1,h,arr);
else
binary_search(l,mid,arr);
}
int main() {
int arr[]={5,9,13,1,3};
printf("found at: %d\n", binary_search(0,4,arr));
return 0;
}
A simple method in Ruby
def CircularArraySearch(a, x)
low = 0
high = (a.size) -1
while low <= high
mid = (low+high)/2
if a[mid] == x
return mid
end
if a[mid] <= a[high]
if (x > a[mid]) && (x <= a[high])
low = mid + 1
elsif high = mid -1
end
else
if (a[low] <= x) && (x < a[mid])
high = mid -1
else
low = mid +1
end
end
end
return -1
end
a = [12, 14, 18, 2, 3, 6, 8, 9]
x = gets.to_i
p CircularArraySearch(a, x)
Though approved answer is optimal but we can also do with a similar and cleaner algorithm.
- run a binary search to find pivot element (where the array is rotated).
O(logn) - left half of the pivot will be sorted in decreasing order, run a backward binary search here for the key.
O(logn) - right half of the pivot will be sorted in increasing order, run a forward binary search in this half for the key.
O(logn) - return found key index from step 2 and 3.
Total Time Complexity: O(logn)
Thoughts welcome.
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.
