Keitaro Urashima Keitaro Urashima - 2 months ago 22
Javascript Question

Binary search not run?

I tried to use binary search algorithm in my code example but It does not run as my expect. I dont know why. Please explain for me

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
var firstIndex = 0;
var lastIndex = array.length - 1;
var currentIndex;
var currentElement;

currentIndex = (lastIndex + firstIndex) / 2 | 2;
currentElement = array[currentIndex];

while (firstIndex <= lastIndex) {
if (numberToSearch === currentElement) {
// found
console.log(currentIndex);
return currentIndex;
} else if (numberToSearch < currentElement) {
lastIndex = currentIndex - 1;
currentIndex = (lastIndex + firstIndex) / 2 | 2;
currentElement = array[currentIndex];
} else if (numberToSearch > currentElement) {
firstIndex = currentIndex + 1;
currentIndex = (lastIndex + firstIndex) / 2 | 2;
currentElement = array[currentIndex];
}
}
return -1;
}
binarySearch(array, 12);


I should print: 5 but nothing happend

Answer Source

What is wrong with your code:

  1. It should be var currentIndex = (lastIndex + firstIndex) / 2 | 0; (not | 2);

  2. currentIndex and currentElement should be calculated at each iteration inside the loop.

So, this is the corrected version of your code:

var array = [1, 4, 6, 8, 9, 12, 15, 17, 19, 34, 55, 78, 80];

function binarySearch (array, numberToSearch) {
var firstIndex = 0;
var lastIndex = array.length - 1;

while (firstIndex <= lastIndex) {
    var currentIndex = (lastIndex + firstIndex) / 2 | 0;
    var currentElement = array[currentIndex];
    if (numberToSearch === currentElement) {
        return currentIndex;
    } else if (numberToSearch < currentElement) {
        lastIndex = currentIndex - 1;
    } else if (numberToSearch > currentElement) {
        firstIndex = currentIndex + 1;
    }
}
 return -1;
}

console.log(binarySearch(array, 99)); // -1
console.log(binarySearch(array, 12)); // 5

BTW, this var currentIndex = (lastIndex + firstIndex) / 2 | 0; looks quite unusual. The common way is var currentIndex = Math.floor((lastIndex + firstIndex) / 2);