*856*

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