Searching an Element in a Rotated Sorted Array

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.

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.

Some Test Cases:

{ 1 }
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

VN:F [1.9.22_1171]
Rating: 4.8/5 (37 votes cast)
Searching an Element in a Rotated Sorted Array, 4.8 out of 5 based on 37 ratings

47 thoughts on “Searching an Element in a Rotated Sorted Array

    1. daxingqiao

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

      VA:F [1.9.22_1171]
      0
      1. Deepak

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

        VA:F [1.9.22_1171]
        0
      2. Deepak

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

        VA:F [1.9.22_1171]
        -1
    2. vran

      How about this one –

      VA:F [1.9.22_1171]
      +1
  1. johny

    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?

    VA:F [1.9.22_1171]
    -1
  2. Ranga

    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.

    VA:F [1.9.22_1171]
    0
  3. raullen

    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;
    }

    VA:F [1.9.22_1171]
    0
  4. Pingback: Searching an Element in a Rotated Sorted Array | 口├人人│의 Blog

  5. nihi

    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.

    VA:F [1.9.22_1171]
    0
  6. ds

    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;
    }

    VA:F [1.9.22_1171]
    -1
    1. dilbert

      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

      VA:F [1.9.22_1171]
      +1
      1. ds

        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.

        VA:F [1.9.22_1171]
        0
  7. maxq

    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;
    }

    VA:F [1.9.22_1171]
    0
    1. maxq

      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;
      }

      VA:F [1.9.22_1171]
      0
  8. Pingback: Searching an Element in a Rotated Sorted Array | laibinshi

  9. napster

    //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;

    }

    }

    VA:F [1.9.22_1171]
    0
  10. jadas

    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

    VA:F [1.9.22_1171]
    0
  11. saurabh Mimani

    Here is one recursive solution:

    VA:F [1.9.22_1171]
    -1
  12. Srikant Aggarwal

    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.

    VA:F [1.9.22_1171]
    0
    1. Brady Fang

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

      VA:F [1.9.22_1171]
      0
    2. Brady Fang

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

      VA:F [1.9.22_1171]
      0
    3. Brady Fang

      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.

      VA:F [1.9.22_1171]
      0
    4. Brady Fang

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

      VA:F [1.9.22_1171]
      0
  13. Pingback: Searching an Element in a Rotated Sorted Array - JavaScript - GeniusCarrier

  14. pankaj

    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;
    }
    }

    VA:F [1.9.22_1171]
    0
  15. Pingback: Search in Rotated Sorted Array | @Siqi

  16. Scott

    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.

    VA:F [1.9.22_1171]
    +2
  17. Pingback: [LeetCode] Search in Rotated Sorted Array (Java) | Life In Code

  18. Pingback: C语言实现数组的就地旋转 | 书影博客

  19. Mannu

    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

    VA:F [1.9.22_1171]
    0
  20. Pingback: Interview - Jung's Wiki

  21. Arun

    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.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*