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)

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

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