## Find an element in an Array of length N which is rotated at point K

0 / 900 Problem :-    Given a sorted and rotated array (rotated at some point) A[ ], and given an element K, the task is to find the index of the given element K in the array A[ ]. The array has no duplicate elements. If the element does not exist in the array, print -1.

Input:
The first line of the input contains an integer T, depicting the total number of test cases. Then T test cases follow. Each test case consists of three lines. First line of each test case contains an integer N denoting the size of the given array. Second line of each test case contains N space separated integers denoting the elements of the array A[ ]. Third line of each test case contains an integer K denoting the element to be searched in the array.

Output:
Corresponding to each test case, print in a new line, the index of the element found in the array.  If element is not present, then print -1.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 100005
0 ≤ A[i] ≤ 10000005
1 ≤ k ≤ 100005

Example:
Input
3
9
5 6 7 8 9 10 1 2 3
10
3
3 1 2
1
4
3 5 1 2
6

Output
5
1
-1

Algorithm:

The algorithm for this is an extended version of binary search. Steps below

1) Find the middle point of the array

2) Divide the array in 2 halves and check if the first half is sorted or not.

3)If first half is sorted, check if the key/element to be searched is between 0 to middle point. If yes, repeat steps 2,3,4. If not, move the search to the next half of the first array sub half and repeat steps 2,3,4 until the complete array is processed

4)If first half isn’t sorted as checked in step 3, move the search to the next half of the full array and repeat the steps 2,3,4 until the complete array is processed.

5)Return the index of the element/key if found else return -1 once control comes out of the loop.

Below is the algorithm implementation in Javascript

 123456789101112131415161718192021222324252627282930 function findElementInRotatedArray(arr, l, h, key) {     while (l < = h) {         // find the middle point of the array         var pivot = parseInt((l + h) / 2);         if (arr[pivot] === key) {             return pivot;         }         // compare extremes of the first half of the array to determine if its sorted or not         if (arr[l] < arr[pivot]) {             // check where is the key located - sub-array first half or second half             if (arr[l] <= key && key <= arr[pivot]) {                 // key lies in the first half                 h = pivot - 1;             } else {                 l = pivot + 1;             }         } else {             // check where is the key located - array first half or second half             if (arr[pivot] <= key && key <= arr[h]) {                 l = pivot + 1;             } else {                 h = pivot - 1;             }         }     }     return -1; }

The algorithm should complete in O(log N) time complexity as binary search. Try the below code in online IDE here

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 init(); function init() {     var array1 = [100000000, 100000001, 100000002, 100000004, 100000007, 100000009, 1000000010,         1000000011, 1000000012, 1000000013, 1, 7889, 45678, 9999999     ];     var array2 = [5, 6, 7, 8, 9, 10, 1, 2, 3];     var array3 = [3, 1, 2];     var array = array1;     for (var i = 0; i < array.length; i++) {         console.log("Finding ", array[i], "in", array, "Found at index", findElementInRotatedArray(array, 0, array.length - 1, array[i]));     }     var array = array2;     for (var i = 0; i < array.length; i++) {         console.log("Finding ", array[i], "in", array, "Found at index", findElementInRotatedArray(array, 0, array.length - 1, array[i]));     }     var array = array3;     for (var i = 0; i < array.length; i++) {         console.log("Finding ", array[i], "in", array, "Found at index", findElementInRotatedArray(array, 0, array.length - 1, array[i]));     } } function findElementInRotatedArray(arr, l, h, key) {     while (l <= h) {         // find the middle point of the array         var pivot = parseInt((l + h) / 2);         if (arr[pivot] === key) {             return pivot;         }         // compare extremes of the first half of the array to determine if its sorted or not         if (arr[l] < arr[pivot]) {             // check where is the key located - sub-array first half or second half             if (arr[l] <= key && key <= arr[pivot]) {                 // key lies in the first half                 h = pivot - 1;             } else {                 l = pivot + 1;             }         } else {             // check where is the key located - array first half or second half             if (arr[pivot] <= key && key <= arr[h]) {                 l = pivot + 1;             } else {                 h = pivot - 1;             }         }     }     return -1; }