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.

 

 

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.

 

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: