Element in sorted rotated array

Element in sorted rotated array

In last post Find minimum element in sorted rotated array, we discussed how to find minimum element in a sorted rotated array. Today’s problem is to find any given element in sorted rotated array. For example:

A = [2,3,4,1] Key = 4, Returns 2 which is position of 4 in array
A = [4,5,6,1,2,3] Key = 4 returns 0

This problem become interesting when duplicate or negative numbers are allowed. Hence, ask interviewer if duplicate elements are allowed and if negative numbers are allowed in array?

Methods to find element in sorted rotated array

Brute force 

Simple solution will be to scan through the array and find element in array as required. This algorithm has O(N) time complexity.

Binary search

Can we do better than brute force solution? Can we apply binary search algorithm here? How to eliminate subarrays? Let’s take couple of examples to understand the strategy:

Find element in sorted rotated array

 

In above example, key to be searched in first case is 5. Take mid and compare it with start of the array, here a[start] < a[end], (4<7) so the lower part is sorted, nothing can be said about the upper part. Now since key lies between a[start] and a[mid], discard the upper part and search again in lower part.
If the key is to be searched is 2, again it can be found that lower array is sorted, but since key to be search in not bound by a[start] and a[mid], search in upper array.

Algorithm to find element in sorted rotated array

If mid is equal to element we are looking for, return mid.
Case 1 :
1. If the lower half of the array is sorted. 
2. Check if A[mid] >= A[start] Check if the element being looked for is greater than A[start]  and less than A[mid] 
3. Discard the upper array we have to look in lower array.  
4. Else look in upper subarray.
Case 2 :
1. If lower array is not sorted that is A[mid] <= A[start] 
2. If element is greater than A[mid] && less than A[end], look in upper sub array.
3. Else look in lower sub array.
Recursive implementation

Iterative implementation

Complexity of above recursive and iterative algorithm to find an element in rotated sorted array is O(log n).

Please share if you have some questions or suggestions. Also, if you want to contribute on this, please contact us.