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)

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

You may also like

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