Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently? You may assume no duplicate exists in the array.
Note:
I have updated the problem description to assume that there exists no duplicate in the array. Some readers have noted that the below code does not work for input with duplicates. For example, for input “1 2 1 1 1 1”, the binary search method below would not work, as there is no way to know if an element exists in the array without going through each element one by one.
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.
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., 4 5 6 7 0 1 2 consists of two sub-arrays 4 5 6 7 and 0 1 2.
Do not jump to conclusion that we need to first find the location of the pivot and then do binary search on both sub-arrays. Although this can be done in O(lg n) time, this is not necessary and is more complicated.
In fact, we don’t need to know where the pivot is. Look at the middle element (7). Compare it with the left most (4) and right most element (2). The left most element (4) is less than (7). This gives us valuable information — All elements in the bottom half must be in strictly increasing order. Therefore, if the key we are looking for is between 4 and 7, we eliminate the upper half; if not, we eliminate the bottom half.
When left index is greater than right index, we have to stop searching as the key we are finding is not in the array.
Since we reduce the search space by half each time, the complexity must be in the order of O(lg n). It is similar to binary search but is somehow modified for this problem. In fact, this is more general than binary search, as it works for both rotated and non-rotated arrays.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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; } |
The above solution is able to search for an element without knowing where the pivot is. Challenge yourself with the problem below.
Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.
Solution:
This time you have to search for the rotation pivot. There is a subtle observation. This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int FindSortedArrayRotation(int A[], int N) { int L = 0; int R = N - 1; while (A[L] > A[R]) { int M = L + (R - L) / 2; if (A[M] > A[R]) L = M + 1; else R = M; } return L; } |
Some Test Cases:
return 0
{ 1, 2 }
return 0
{ 2, 1 }
return 1
{ 1, 2, 3 }
return 0
{ 3, 1, 2 }
return 1
{ 2, 3, 1 }
return 2
{ 1, 2, 3, 4, 5 }
return 0
{ 2, 3, 4, 5, 1 }
return 4
{ 3, 4, 5, 1, 2 }
return 3
{ 4, 5, 1, 2, 3 }
return 2
{ 5, 1, 2, 3, 4 }
return 1
{ 1, 2, 3, 4, 5, 6 }
return 0
{ 2, 3, 4, 5, 6, 1 }
return 5
{ 3, 4, 5, 6, 1, 2 }
return 4
{ 4, 5, 6, 1, 2, 3 }
return 3
{ 5, 6, 1, 2, 3, 4 }
return 2
{ 6, 1, 2, 3, 4, 5 }
return 1
{ 6, 8, 1, 2, 4, 5 }
return 2
Your code breaks when I provide it these inputs:
key: 0
A: [1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
output: -1
Yes, it does not work. For this case, it’s a little difficult, it’s hard to determine the direction in the next iteration.
To detect an array(or its subarray) is sorted and rotated we need to check a[start] > a[end]
if you find a mid of a sortated rotated array it can do the following things
* partition array in two pieces A) “sorted roated array” B) “sorted array”
* partition array on two pieces A) “sorted array” B) “sorted rotated Array”
* partition array in two pieces A) “sorted array” B) “sorted array” in this case it will be max item or min item.
*/
/* logn complexity */
To detect an array(or its subarray) is sorted and rotated we need to check a[start] > a[end]
if you find a mid of a sortated rotated array it can do the following things
* partition array in two pieces A) “sorted roated array” B) “sorted array”
* partition array on two pieces A) “sorted array” B) “sorted rotated Array”
* partition array in two pieces A) “sorted array” B) “sorted array” in this case it will be max item or min item.
*/
/* logn complexity */
How about this one –
For the second problem, why is finding the amount of rotation equivalent to finding the minimal value’s index? Is there any mathematical reasoning involved?
you are confused, the finding rotation pivot is equal to finding the minimal value’s index.
Hi,
I couldn’t find any other way to contact you to ask this question.
I’ve been trying to find a solution which runs better than O (n * logn) for using binary search in a 2-D sorted Array, where all the rows and columns are sorted.
Thanks for your help and your continued efforts.
try this
int FindSortedArrayRotation(){
int min = 0, max = input_len-1, middle;
while(min input_rotate[max])
return max;
if(input_rotate[middle] > input_rotate[max]){
//pivot in the right
min = middle;
}
else{
//pivot in the left
max = middle;
}
}
return -1;
}
Pingback: Searching an Element in a Rotated Sorted Array | 口├人人│의 Blog
if A[L] = key, why don’t we return? The same as when we get A[R] == key is true. Other than that, clear and nice.
Actually this question is simple to solve as it doesn’t have that many edge cases. Try this question which is similar to this but has a lot more edge cases – “Given an array which is monotonically increasing order till certain point and started decreasing after that point. Find whether a number exist in it or not”. Ex: {1,3,5,7,11,9,6,2} Find whether 6 exist or not.
I think it is logically easier if you find the pivot first, then do two binary search. How about that?
It doesn’t work. Try {3,2,8,6,5}, it returns -1 for 6. Or {10,5,4,20,12}, returns -1 for 10.
By comparing A[M] with A[l], the assumption “All elements in the bottom half must be in strictly increasing order.” is not valid.
Here is my code. The assumption is that there is no duplicate in the array. Otherwise it needs more work to determine the order.
//Assume there is no duplicate in the array.
public static int rotated_binary_search_r(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[R])
{//previous array before rotation before rotation is descending
if (A[M] < A[L])
{
if (key == A[L])
return L;
if (A[M] < key && key < A[L])
R = M – 1;
else
L = M + 1;
}
else
{
if (key == A[R])
return R;
if (A[R] < key && key A[L])
{
if (key == A[L])
return L;
if (A[L] < key && key < A[M])
R = M – 1;
else
L = M + 1;
}
else
{
if (key == A[R])
return R;
if (A[M] < key && key < A[R])
L = M + 1;
else
R = M – 1;
}
}
}
return -1;
}
Assumption is that we are finding an element in a sorted (ascending order) array, which is rotated. In your case it doesnt work because its not a valid input
I don’t understand why my cases are not valid? {8,6,5,3,2} is sorted array and it can be rotated to {3,2,8,6,5}; Or {20,12,10,5,4} can be rotated to {10,5,4,20,12}.
Sorted array doesn’t have to be ascending order. Even so we may find a not working case.
For the second problem, it’s probably better to use L <R as termination condition,
more easier to understand. I've tested the below code works for all your inputs.
int FindSortedArrayRotation(int A[], int N) {
int L = 0;
int R = N – 1;
while (L A[R])
L = M + 1;
else
R = M;
}
return L;
}
Sorry, the code should be:
int FindSortedArrayRotation(int A[], int N) {
int L = 0;
int R = N – 1;
while (L < R)
L = M + 1;
else
R = M;
}
return L;
}
Pingback: Searching an Element in a Rotated Sorted Array | laibinshi
//try using this, this works for every test case
//Time Complexity is O(log n)
public class SearchRotatedSortedArray
{
public static void main(String… args)
{
int[] array={5,6,1,2,3,4};
System.out.println(search(array,Integer.parseInt(args[0]),0,5));
}
public static boolean search(int[] array,int element,int start,int end)
{
if(start>=end)
{
if (array[end]==element) return true;else return false;
}
int mid=(start+end)/2;
if(array[start]<array[end])
{
return binarySearch(array,element,start,end);
}
return search(array,element,start,mid)||search(array,element,mid+1,end);
}
public static boolean binarySearch(int[] array,int element,int start,int end)
{
int mid;
while(start<=end)
{
mid=(start+end)/2;
if(array[mid]==element)
return true;
if(array[mid]<element)
{
start=mid+1;
}
else
{
end=mid-1;
}
}
return false;
}
}
napster is amitveerani@gmail.com
Does sorting means it is in ascending order? Lets say my array was descending and got rotated. eg
20 18 3 200 100 (rotated)
200 100 20 18 3(Original)
The solution will not work i think
Here is one recursive solution:
I didnt understand the use of some boundary conditions.Please help.
Why while finding the element u used while(L <= R) and not (L < R)and in finding pivot u used (A[L] < A[R]) and not (A[L] <= A[R]).
Also while updating the R in finding pivot element u update it to M and not M-1.
While u updated L to M+1 and not M.
In searching for a element, three cases were treated, namely, (1) A[M] == key; (2) A[L] <= key < A[M]; (3) A[M] < key A[R]; (2) A[M] <= A[R]. You would update L as L = M+1 in (1), and update R as R = M in (2).
My previous comment failed to fully appear…
In searching for a element, three cases were treated, namely, (1) A[M] == key; (2) A[L] <= key < A[M]; (3) A[M] < key A[R]; (2) A[M] <= A[R]. You would update L as L = M+1 in (1), and update R as R = M in (2).
In searching for a element, three cases were treated, namely, (1) A[M] == key; (2) A[L] <= key < A[M]; (3) A[M] < key <= A[R]. Obviously, you should update R as R = M-1 in (2), and update L as L = M+1 in (3). In addition, as the searching space narrows, it is possible that L and R could be the index to the same element, which is exactly what intended to search for.
By contrast, in searching for the pivot, two cases were treated, i.e., (1) A[M] > A[R]; (2) A[M] <= A[R]. You would update L as L = M+1 in (1), and update R as R = M in (2).
Hey blog admin want to make money with your blog? http://goo.gl/shDWH
Try out this recursive solution!!! This was my first thought.
http://innosamcodes.wordpress.com/searching-an-element-in-a-rotated-sorted-array/
THIS GUY SEEMS TO HAVE COPIED FROM HERE ITSELF : http://how-to-crack-algorithms.blogspot.in/2011/09/searching-element-in-rotated-sorted.html
Moron, first check the dates when post was published! Leetcode is a respected site!
Good work. Have a look at my approach at http://knavite.blogspot.in/2013/11/searching-element-in-rotated-sorted.html . Please give feedback.
Pingback: Searching an Element in a Rotated Sorted Array - JavaScript - GeniusCarrier
Accepted solution in leetcode
public class Solution {
public boolean search(int[] A, int target) {
int start = 0;
int end = A.length – 1;
while (start <= end) {
int mid = start + (end – start) / 2;
if (A[mid] == target) {
return true;
} else if (A[start] < A[mid]) {
if (A[start] <= target && target A[mid]) {
if (A[end] >= target && target > A[mid]) {
start = mid + 1;
} else {
end = mid – 1;
}
} else { // for repeated element don’t know where to go
if (A[end] < target) {
end = end – 1;
} else {
start = start + 1;
}
}
}
return false;
}
}
Hi, i see what you meant, but how to find the max number 7?
Nice concept.
The problem statement should mention that it is an ascending order. Otherwise, the code doesn’t work.
Pingback: Search in Rotated Sorted Array | @Siqi
I think there’s a problem with the approach. Look at this statement from the post:
“When left index is greater than right index, we have to stop searching as the key we are finding is not in the array.”
This still assumes that the middle element is where the pivot ends. What if the pivot is slightly off and the array is {5, 6, 7, 0, 1, 2, 4} and the target element is 4.
In that case, when you look at the middle element and see “0” you will then say, “Oh, the left element 5 is greater than 0, therefore 4 is not in the array” and give up, but this would be incorrect.
Pingback: [LeetCode] Search in Rotated Sorted Array (Java) | Life In Code
Pingback: C语言实现数组的就地旋转 | 书影博客
Request to suggest solution for the following sorting problem
Input: Any random array eg. {12, 45, 2, 56, 1}
Output: { 1 12 56 45 2}, like middle element is the largest one and second max is right, then 3rd max is in left and so on.
Thanks in advance
Pingback: Interview - Jung's Wiki
Use BST u will be able to find the key in logn time complexity
Why do we do int M = L + ((R – L) / 2)
and not M=(L+R)/2
In my code if i do the 2nd one, i get an overflow error. but how does normal binary search code works with the 2nd line.
Very nice article. I also wrote a detailed analysis of the same problem here https://goo.gl/szIOuC