Searching in a sorted and rotated array
Solution 1
This can be done in O(logN)
using a slightly modified binary search.
The interesting property of a sorted + rotated array is that when you divide it into two halves, atleast one of the two halves will always be sorted.
Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements = 9
mid index = (0+8)/2 = 4
[4,5,6,7,8,9,1,2,3]
^
left mid right
as seem right sub-array is not sorted while left sub-array is sorted.
If mid happens to be the point of rotation them both left and right sub-arrays will be sorted.
[6,7,8,9,1,2,3,4,5]
^
But in any case one half(sub-array) must be sorted.
We can easily know which half is sorted by comparing start and end element of each half.
Once we find which half is sorted we can see if the key is present in that half - simple comparison with the extremes.
If the key is present in that half we recursively call the function on that half
else we recursively call our search on the other half.
We are discarding one half of the array in each call which makes this algorithm O(logN)
.
Pseudo code:
function search( arr[], key, low, high)
mid = (low + high) / 2
// key not present
if(low > high)
return -1
// key found
if(arr[mid] == key)
return mid
// if left half is sorted.
if(arr[low] <= arr[mid])
// if key is present in left half.
if (arr[low] <= key && arr[mid] >= key)
return search(arr,key,low,mid-1)
// if key is not present in left half..search right half.
else
return search(arr,key,mid+1,high)
end-if
// if right half is sorted.
else
// if key is present in right half.
if(arr[mid] <= key && arr[high] >= key)
return search(arr,key,mid+1,high)
// if key is not present in right half..search in left half.
else
return search(arr,key,low,mid-1)
end-if
end-if
end-function
The key here is that one sub-array will always be sorted, using which we can discard one half of the array.
Solution 2
The accepted answer has a bug when there are duplicate elements in the array. For example, arr = {2,3,2,2,2}
and 3 is what we are looking for. Then the program in the accepted answer will return -1 instead of 1.
This interview question is discussed in detail in the book 'Cracking the Coding Interview'. The condition of duplicate elements is specially discussed in that book. Since the op said in a comment that array elements can be anything, I am giving my solution as pseudo code in below:
function search( arr[], key, low, high)
if(low > high)
return -1
mid = (low + high) / 2
if(arr[mid] == key)
return mid
// if the left half is sorted.
if(arr[low] < arr[mid]) {
// if key is in the left half
if (arr[low] <= key && key <= arr[mid])
// search the left half
return search(arr,key,low,mid-1)
else
// search the right half
return search(arr,key,mid+1,high)
end-if
// if the right half is sorted.
else if(arr[mid] < arr[high])
// if the key is in the right half.
if(arr[mid] <= key && arr[high] >= key)
return search(arr,key,mid+1,high)
else
return search(arr,key,low,mid-1)
end-if
else if(arr[mid] == arr[low])
if(arr[mid] != arr[high])
// Then elements in left half must be identical.
// Because if not, then it's impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high]
// Then we only need to search the right half.
return search(arr, mid+1, high, key)
else
// arr[low] = arr[mid] = arr[high], we have to search both halves.
result = search(arr, low, mid-1, key)
if(result == -1)
return search(arr, mid+1, high, key)
else
return result
end-if
end-function
Solution 3
You can do 2 binary searches: first to find the index i
such that arr[i] > arr[i+1]
.
Apparently, (arr\[1], arr[2], ..., arr[i])
and (arr[i+1], arr[i+2], ..., arr[n])
are both sorted arrays.
Then if arr[1] <= x <= arr[i]
, you do binary search at the first array, else at the second.
The complexity O(logN)
EDIT: the code.
Solution 4
My first attempt would be to find using binary search the number of rotations applied - this can be done by finding the index n where a[n] > a[n + 1] using the usual binary search mechanism. Then do a regular binary search while rotating all indexes per shift found.
Solution 5
int rotated_binary_search(int A[], int N, int key) {
int L = 0;
int R = N - 1;
while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == key) return M;
// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}
Comments
-
Jones almost 3 years
While preparing for an interview I stumbled upon this interesting question:
You've been given an array that is sorted and then rotated.
For example:
- Let
arr = [1,2,3,4,5]
, which is sorted - Rotate it twice to the right to give
[4,5,1,2,3]
.
Now how best can one search in this sorted + rotated array?
One can unrotate the array and then do a binary search. But that is no better than doing a linear search in the input array, as both are worst-case O(N).
Please provide some pointers. I've googled a lot on special algorithms for this but couldn't find any.
I understand C and C++.
- Let
-
Jones over 13 yearsThanks max but I don't understand how will you apply your first BS?
-
Jones over 13 yearsI mean what will be your search key ?
-
Jones over 13 yearsWhat will be your search key when doing a BS to find number of rot ?
-
Steve Jessop over 13 years@Jones: it would be a modified binary search. You're looking for a point at which two adjacent values decrease. Guess an index. If the value at that index is greater than the first value in the array then keep looking on the right hand side of your guess. If it's less, keep looking on the left. But codaddict's answer is better if you don't actually care where the discontinuity is, you just want to perform a search.
-
Max over 13 years@Jones, it is easier to write code then to explain. I edited answer, look for the link.
-
ruslik over 13 yearsWhy do you have to search explicitely for the "breaking point"? Why don't use a modified binary search directly to search the element and in the same time to check for "anomalies"?
-
Ashwin about 11 yearsSimple. Concise. Examples. FTW !!
-
Tomato about 9 yearsI think you're the only one who considered repeated elements properly. But your approach doesn't guarantee logarithmic complexity. Especially on an input such as 5,5,5,5,5,5, ... (lots of fixes), 5,1, 5
-
Bharat Soni over 8 yearsand thats why I like Stackoverflow, you always get a new and best approach to solve the problem. Thanks @codeaddict
-
kaushal almost 8 yearsAs mentioned above, this won't handle the case of duplicate entries. However, if elements are unique, this is a very simple code since it doesn't do any recursion.
-
Shadab Ansari almost 8 yearsWhat should be the change in the solution to accommodate the duplicates as this does not woks for array with duplicates like searching "15" in
{10, 15, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}
? -
Ehtesh Choudhury over 7 years@ShadabAnsari I think that would be a different answer entirely. This is easier to follow with nested conditions, as it lets you focus only on the sorted sub-array. I was having trouble by thinking about the entire array instead of only a portion of it.
-
wild_nothing almost 7 years"The interesting property of a sorted + rotated array is that when you divide it into two halves, at least one of the two halves will always be sorted." This separates the genius or the experienced from the novice. Thank-you, this one line helped me visualise the entire solution.
-
Prashanth Debbadwar almost 5 yearsWhat is the time complexity if we have repeated elements?
-
Sam Kah Chiin about 4 yearsThis is the best explanation I can find for this question.
-
Manjeet Thakur about 4 years[1, 3] if I try to find 3 then the output is incorrect
-
Sopel about 4 yearsI think it has to be linear if duplicates are allowed. Consider a list of N
1
s with one2
somewhere. It can be anywhere and it will be a valid input. We're looking for that2
. No matter what range of M>2 numbers we consider, if the2
is not on any of the sides we cannot tell whether it's contained in those M numbers or not. So you cannot narrow the search in any way that helps. -
Jaydeep Shil over 3 yearsI am late here, I have been asked the same question, I did not solve it in O(logn), my solution was little improved of O(n). My approach was two pointer i = 0 and j = size() - 1, in a loop check arr[i] == key or arr[j] == key if found return i or j and break, else icrement i and decrement j , break condition was i < j, in this case loop will run in worst case n/2 nos of time if the key is present in the middle
-
iwrestledthebeartwice about 3 yearsHow does it become
O(logN)
, when you are searching for the indexi
i.e., the pivot point, you must traverse the entire array if the input is1,2,3,4,5,6,7,8,9
which is O(N) then you'll perform the binary search. So, the overall complexity will be O(N). -
Ryan almost 3 yearsThis answer uncovered what I was missing. I understand the properties of this problem now. Like @wild_nothign mentioned, the property of "least one of the two halves will always be sorted" helped me understand this problem greatly. At least of the two halves will always be sorted (which must include the pivot index element )
-
Ruhshan over 2 years"least one of the two halves will always be sorted" This is just what I needed.. thanks maestro!