Ad
Improve Speed Of My Binary Search Algorithm
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;
}
Ad
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; }
Ad
source: stackoverflow.com
Related Questions
- → How to update data attribute on Ajax complete
- → October CMS - Radio Button Ajax Click Twice in a Row Causes Content to disappear
- → Octobercms Component Unique id (Twig & Javascript)
- → Passing a JS var from AJAX response to Twig
- → Laravel {!! Form::open() !!} doesn't work within AngularJS
- → DropzoneJS & Laravel - Output form validation errors
- → Import statement and Babel
- → Uncaught TypeError: Cannot read property '__SECRET_DOM_DO_NOT_USE_OR_YOU_WILL_BE_FIRED' of undefined
- → React-router: Passing props to children
- → ListView.DataSource looping data for React Native
- → Can't test submit handler in React component
- → React + Flux - How to avoid global variable
- → Webpack, React & Babel, not rendering DOM
Ad