Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 29, 2018 02:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/5851b06ab90389b2477b7514e0ad1f85 to your computer and use it in GitHub Desktop.
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
/*
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