I have written a binary search algorithm in JavaScript:
function binarysearch(number, array) { let left = 0; let right = array.length - 1; let middle; while (right != left) { middle = Math.floor(left + (right - left) / 2); if (array[middle] == number) { return middle; } if (array[middle] < number) { left = array[middle]; if (array[middle + 1] == number) { return middle + 1; } } if (array[middle] > number) { right = array[middle]; if (array[middle - 1] == number) { return middle - 1; } } } return -1; }
I wanted to ask if I can improve this algorithm to search faster or if some mistake is made here?
EDIT:
thank you guys for your help, this solution should work correctly now:
function binarysearch(number, array) { let left = 0; let right = array.length - 1; let middle; while (left <= right) { middle = Math.floor(left + (right - left) / 2); if (array[middle] == number) { return middle; } if (array[middle] < number) { left = middle + 1; } if (array[middle] > number) { right = middle - 1; } } return -1; }
Advertisement
Answer
You are taking values as indices. If you take greater values than indices, you see your codes does not work.
Instead, you could take the index of middle
for left
or right
if not found.
function binarysearch(number, array) { let left = 0, right = array.length - 1, middle; while (left <= right) { middle = Math.floor((left + right) / 2); if (array[middle] === number) return middle; if (array[middle] > number) right = middle - 1; else left = middle + 1; } return -1; } console.log(binarysearch(0, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(43, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(44, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(45, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(46, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(47, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(48, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(49, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(50, [43, 44, 45, 46, 47, 48, 49, 50])); console.log(binarysearch(100, [43, 44, 45, 46, 47, 48, 49, 50]));
.as-console-wrapper { max-height: 100% !important; top: 0; }