Question: Given a sorted array of n integers that has been rotated an unknown number of times, give a O(log (n)) solution that finds an element in the array?
Input: arr [] = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}. Find 5 .
Output: 8 (the index of 5 in the array)
Let us assume that the given array is arr[]. The basic approach for this problem will be:-
- Find the pivot element. That means after which all elements are in ascending order. This basically tells how many times the array has been rotated.
Example:-
If a sorted array is as:- {4, 8, 15, 16, 23, 42}
Rotating it once will give:- {42, 4, 8, 15, 16, 23}, The pivot is the 2nd element = 4
Rotating it 3 times will give:- {16, 23, 42, 4, 8, 15}, The pivot is the 4th element = 4Implies, that if we already know how many times the array has been rotated, we can skip this step. - By the above step. The array is divided in 2 “sorted” halves.
-> From the 1st element to pivot,
-> and from the pivot element to the last element.
If the element to be searched is greater than the 1st element of the array, that means it lies in the first half, else it lies in the second half. - Now searching in O(log(n)) time can only be done by Binary Search. Just perform a binary search on the respective half of the array and we will get our index.
Finding the Pivot Element
The main idea for finding the pivot element is – “for a sorted (in increasing order), and pivoted array, pivot element is the only element for which the previous element to it is greater than itself.”
Thus, one way to find the pivoted element could be traverse the array and check the previous element. If the previous element is greater, then we have the pivot element. But this approach is very long and will not work in O(log(n)) time. Again we shall try to use binary search to find the pivot element. We shall use the above definition of pivot element for our help.
//find pivot element using binary search.
int findPivot(int arr[], int size)
{
if(arr[0] < arr[size-1])
{
//means that the array is not rotated at all.
//the first element is the pivot element
return 0;
}
// setting the first and last for binary search
int start = 0;
int finish = size-1;
int mid;
while(start < finish)
{
mid = start + (finish - start)/2;
if(arr[start] < arr[mid])
{
//means that the first half is sorted completely
//our pivot is in second half
start = mid;
}
else
{
//means that the second half is sorted completely
//our pivot is in first half
finish = mid;
}
}
//as the loop finishes, 'mid' points at the largest element in the array
//so we return the next element as our pivot.
return (mid+1);
}
Searching for the Element
Now that we have the pivot element we have our array in two parts:-
- arr[0]…..arr[pivot-1]
- arr[pivot]……arr[size-1]
Our element to be searched can be found only in these limits. We just check if our element is larger than arr[0]. If yes, then definitely our element lies in the first half, else in the second half.
//helper function
int binarySearchIterative(int arr[], int low, int high, int data)
{
int mid;
while(low<=high)
{
mid = low + (high-low)/2;
if(arr[mid] == data)
return mid;
else
{
if(arr[mid] < data)
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
// function to search the element in the array
// returns -1 if the element is not found
int search(int arr[], int size, int data)
{
int pivot = findPivot(arr, size);
int index = -1;
if(pivot == 0)
{
//the array is not rotated at all
index = binarySearchIterative(arr, 0, size-1, data);
}
else
{
//if the array was rotated and pivot > 0
if(data >= arr[0])
{
// our element lies in the first half.
index = binarySearchIterative(arr, 0, pivot-1, data);
}
else
{
// our element lies in the second half
index = binarySearchIterative(arr, pivot, size-1, data);
}
}
//return the index of the element
return index;
}
Time Complexity:- O (log (n))
You can download the complete working demo of the code here. Use your favorite editor to open the file.
Click here for Method 2 – Using 1 scan.