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

-1Yes, it does not work. For this case, it’s a little difficult, it’s hard to determine the direction in the next iteration.

0To 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 */

0To 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 */

-1How about this one –

+1For the second problem, why is finding the amount of rotation equivalent to finding the minimal value’s index? Is there any mathematical reasoning involved?

-1you are confused, the finding rotation pivot is equal to finding the minimal value’s index.

+2Hi,

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.

0try 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;

}

0Pingback: 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.

0Actually 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.

0I think it is logically easier if you find the pivot first, then do two binary search. How about that?

+1It 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;

}

-1Assumption 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

+1I 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.

0For 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;

}

0Sorry, 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;

}

0Pingback: 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;

}

}

0napster is amitveerani@gmail.com

0Does 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

0Here is one recursive solution:

-1I 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.

0In 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).

0My 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).

0In 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.

0By 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).

0Hey blog admin want to make money with your blog? http://goo.gl/shDWH

+1Try out this recursive solution!!! This was my first thought.

http://innosamcodes.wordpress.com/searching-an-element-in-a-rotated-sorted-array/

0THIS GUY SEEMS TO HAVE COPIED FROM HERE ITSELF : http://how-to-crack-algorithms.blogspot.in/2011/09/searching-element-in-rotated-sorted.html

-1Moron, first check the dates when post was published! Leetcode is a respected site!

+3Good work. Have a look at my approach at http://knavite.blogspot.in/2013/11/searching-element-in-rotated-sorted.html . Please give feedback.

+1Pingback: 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;

}

}

0Hi, i see what you meant, but how to find the max number 7?

0Nice concept.

0The problem statement should mention that it is an ascending order. Otherwise, the code doesn’t work.

0Pingback: 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.

+2Pingback: [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

0Pingback: Interview - Jung's Wiki

Use BST u will be able to find the key in logn time complexity

0Why 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.

0Very nice article. I also wrote a detailed analysis of the same problem here https://goo.gl/szIOuC

0