Created
January 29, 2018 02:24
-
-
Save jianminchen/5851b06ab90389b2477b7514e0ad1f85 to your computer and use it in GitHub Desktop.
Find array index equal element - javascript code written, study code for me to learn JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Binary Search Approach: O(logN) | |
0 1 2 3 4 5 6 | |
[0, 1, 2, 4, 5, 6, 10] | |
l m h | |
l m h | |
Do Binary search until lo is greater than hi | |
mid = Math.floor(lo + hi); | |
- if element is equal to it's index, return index | |
- else if the element is greater than it's index value | |
hi = mid - 1 | |
- else | |
lo = mid + 1 | |
*/ | |
function indexEqualsValueSearch(arr) { | |
let lo = 0; | |
let hi = arr.length - 1; | |
let mid; | |
while (lo <= hi) { | |
mid = Math.floor((lo + hi)/2); | |
if (arr[mid] === mid) { | |
let leftPartition = arr.slice(lo, mid); // exclude mid -> | |
let leftResult = indexEqualsValueSearch(leftPartition); | |
if (leftResult === -1) { | |
return mid; | |
} | |
return leftResult; | |
} | |
else if (arr[mid] > mid) { | |
hi = mid - 1; | |
} | |
else { | |
lo = mid + 1; | |
} | |
} | |
return -1; | |
} | |
let arr1 = [0, 1, 2, 4, 5, 6, 10]; | |
let arr2 = [-8,0,2,5]; | |
let arr3 = [-1,0,3,6]; | |
console.log(indexEqualsValueSearch(arr1)); // 0 | |
console.log(indexEqualsValueSearch(arr2)); // 2 | |
console.log(indexEqualsValueSearch(arr3)); // -1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment