Site icon Study Algorithms

Find an element in a sorted array rotated unknown times. (Method 2)

Question: Given a sorted array of n integers that has been rotated an unknown number of times, give a O(log (n)) solution that finds an element in the array?

Input: arr [] = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}. Find 5 .
Output: 8 (the index of 5 in the array)

We can solve this problem in only one scan of the array as well. Please read Method 1 if you have not done so, as this forms the base of this problem.

To solve the problem in 1 scan we can apply a variation of the Binary Search technique as:-

// function to find an element in a sorted rotated array
// returns -1 if the element is not found
int binarySearchRotated(int arr[], int start, int finish, int data)
{
	int mid;
	
	// terminating condition
	if(start<finish)
		return -1;
		
	mid = start + (finish - start)/2;
		
	if(data == arr[mid])
		return mid;
	else if(arr[start] <= arr[mid])
	{
		if(data >= arr[start] && data < arr[mid])
			return binarySearchRotated(arr, start, mid-1, data);
		else
			return binarySearchRotated(arr, mid+1, finish, data);
	}
	else
	{
		// arr[mid] < = arr[finish], finish half is in sorted order
		if(data > arr[mid] && data <= arr[finish])
			return binarySearchRotated(arr, mid+1, finish, data);
		else
			return binarySearchRotated(arr, start, mid-1, data);
	}
}
Exit mobile version