Search in a sorted but rotated array

A sorted array has been rotated (in one direction) for unknown number of times. Search a value in the array

Note that, if the array was rotated exactly number of times equal to its length then its sorted again. So, we could have done a normal binary search on the sorted array. As the array was rotated only in one direction then it is easy to observe that the part of the array from the min element position (let’s say it rotation pivot) to the end is sorted.

For example: if [1, 2, 3, 4, 5, 6, 7, 8, 9] is rotated right for 5 times then the rotated array is [6, 7, 8, 9, 1, 2, 3, 4, 5].

If the search key in the sorted part of the array then it is easy to find it by doing normal binary search. Otherwise the search key is in the rotated part (i.e. reverse sorted order) and we can perform a reverse order binary search for this. So, the key point is to identify when to perform normal search or search in reverse order.

If we observe closely then we can see the the middle elements in the sorted part is always less than the leftmost element. This is the key to identify the pivot point.

So, idea is to do a binary search on the array. if we are in sorted part and the key is less than the middle then we know that e need to search in left. Other wise we know that the key is in the right of middle element only if it is less than the rightmost element (in which case the search key lies in the rotated part where all elements are greater than the right most element).

If we are in rotated part and the search key is greater than the middle element then we search in the right of the rotated part. Other wise we know that the key is in the left of rotated part only if it is not less then the left most element (in which case the search key is in the sorted part where all elements are less the the leftmost element).

public static int searchInSortedRotatedArray(int a[], int key){
	int l = 0;
	int h = a.length-1;
	int mid;
	
	while(l < h){
		mid = (l+h)/2;
		if(a[mid] == key){
			return mid;
		}
		//search in left subtree
		else if(a[mid] > key){
			//if left subtree has rotated part
			if(a[l] > key){
				l = mid+1; 
			}
			//otherwise its in sorted part
			else{
				h = mid-1;
			}
		}
		else{
			//if right subtree has rotated part
			if(a[h] < key){
				h = mid-1;
			}
			//otherwise its in sorted part
			else{
				l = mid+1;
			}
		}
	}
	
	return -1;
}

A complementary question to this problem could be to identify the rotation pivot position itself. Observe that rotation pivot is the minimum element in the array. Trivial solution would be O(n) with linear search. But we could so better by doing a simple modification of simple binary search.

Observer that the rotation pivot is the left most element of the sorted part of the array. The sorted part of the array id characterized by the fact that leftmost element is less than the rightmost element (i.e. elements are in strictly increasing order). We can do a binary search on the rotated array until we satisfy this condition. While doing binary search, If we are in the rotated part of the array then the middle element is always higher than the rightmost element. So, we should search in the right part of the middle element. If the middle is in sorted part then we continue searching on the left as the right part of middle is in order now.

public static int findRotationPositin(final int[] a) {
    if (a.length <= 1) {
        return 0;
    }

    int l = 0;
    int r = a.length - 1;
    int m = (l + r) / 2;

    while (a[l] > a[r]) {
        m = (l + r) / 2;

        if (a[m] > a[r]) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    return l;
}