What is Rotated Sorted Array
It is nothing but a sorted array, which is twisted/rotated with some pivot element.
So if you observe rotated array then it can be classified as two sub-array that is sorted.
For example your sorted array A:
A = { 0,1,2,3,4,5,6,7,8,9 }
and your rotated sorted array look like this:
A = { 2,3,4,5,6,7,8,9,0,1 }
Now how do you find an element in the rotated array efficiently? You may assume no duplicate exists in the array.
At first look, we know that we can do a linear search in O(n) time. But linear search does not need the elements to be sorted in any way.
To explain the problem consider following array.
array = { 11,12,14,2,3,4,5,6,7,8 }
This is a sorted array and rotate around unknown position,Original array was like:
array = { 2,3,4,5,6,7,8,11,12,14 }
We need to find let’s say 8.
First, we know that it is a sorted array that’s been rotated. Although we do not know where the rotation pivot is, there is a property we can take advantage of.
Here, we make an observation that a rotated array can be classified as two sub-array that is sorted
(i.e 11,12,14,2,3,4,5,6,7,8 consists of two sub-arrays 11,12,14 and 2,3,4,5,6,7,8)
So let’s divide the array the array in two parts. What are the cases we get, there are three cases:
1. Middle element is exactly the rotation point.
2. Middle element is in the left part, in this case a[mid] > a[end] and a[start] < a[mid]
3. Middle element is in the right part, in that case a[mid] < a[end] and a[start] > a[mid]
Based on this analysis we can say that, in case 2, if key is greater that mid , we search in right part of the array. In case, if we key is less than mid, then it can be anywhere, so we need to put another check i.e if key is less than end. If Key is less than end we go to right part, else search in left part of the array.
In case 3, if key is less than mid, all elements on the right side are greater than mid in this case, hence we can look in left part of the array.
In case if key is greater that mid, it can be anywhere. Hence we put additional check i.e. if the key is greater than start. If key greater than start, we need to check in the left part, else look in right part.
int find_element(int a[], int start, int end, int element){
int mid = start +(end-start)/2;
if(a[mid] == element)
return mid;
if(a[mid] < a[end]){
// Case 3 /* If key is greater than mid but less than end look in right part /*
if(element > a[mid] && element <= a[end]){
return find_element(a,mid+1,end, element);
}
/* If element is greater than end, we need to look in left part */
else if (element > a[end]){
return find_element(a, start, mid-1,element);
}
}
/*Case where we are in left part of the rotation */
else if(a[mid] > a[start]){ // Case 2
/*
If key is less than mid and greater than start
look in left part
*/
if(element < a[mid] && element >= a[start] ){
return find_element(a,start,mid-1, element);
}
else
return find_element(a,mid+1,end, element);
}
}
Test cases
Positive test cases
1. A = [11,12,14,2,3,4,5,6,7,8,9]; Key =9
2. A = [11,12,14,2,3,4,5,6,7,8,9]; Key =11
3. A = [11,12,14,2,3,4,5,6,7,8,9]; Key =3
Negative Test cases
1. A = [11,12,14,2,3,4,5,6,7,8,9]; Key =10
2. A = []
Now suppose duplicates are allowed in this, then how we can find element efficiently?
This problem again uses binary search method. Only difference is that we don’t stop as soon as we get the key. We go ahead and check the left part of the array again by dividing it in two halves. As soon as we find the element for the first time, it will be always the end of the sub array. So when we exit the while loop we only need to only check if the end index contains the given element.
Following code is self explanatory.
int first_instance(int a[], int size, int element){
int mid =0;
int start = 0;
int end = size;
while(start<end){
mid = (start + end)/2;
printf("Mid %d :\n", mid);
if(a[mid] < element){
start = mid+1;
}
else{
end = mid;
}
}
if(a[end] == element)
return end ;
else
return -1;
}
Reference: http://leetcode.com/2010/04/searching-element-in-rotated-array.html