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

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

by nikoo28
0 comment

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);
	}
}
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More