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

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

 

[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]

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;

}

[/cc]

 

 

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

 

[cc lang = "javascript" lines="-1" tab_size="4" width="100%"]

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;

}

[/cc]

 

 

---

Posted from my blog with SteemPress : http://www.golibrary.co/find-an-element-in-an-array-of-length-n-which-is-rotated-at-point-k/

---