Searching in a sorted and rotated array

Question

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

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

Answer 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