Find an element in an Array of length N which is rotated at point K
0
/
1218
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | 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; } |