Skip to content

Instantly share code, notes, and snippets.

@clarketm
Last active Apr 8, 2017
Embed
What would you like to do?
Binary Search (JavaScript)
function binarySearch(array, target) {
var startIndex = 0,
stopIndex = array.length - 1,
middle,
count = 0;
while (startIndex < stopIndex) {
count++;
middle = ~~((stopIndex + startIndex) / 2);
// adjust search area
if (target < array[middle]) {
stopIndex = middle - 1;
} else if (target > array[middle]) {
startIndex = middle + 1;
} else {
break; // target is found (or list is exausted)
}
}
// # of iterations
console.log(count + " iterations");
//make sure it's the right value
return (array[middle] === target) ? middle : -1;
}
var array = ["a", "b", "c", "d", "e", "f", "h", "i", "j"];
console.log(binarySearch(array, "i")); // 7 found //=> 3 iterations
console.log(binarySearch(array, "b")); // 1 found //=> 2 iterations
console.log(binarySearch(array, "g")); // -1 not found //=> 2 iterations
@Jason3S
Copy link

Jason3S commented Jan 25, 2017

Maybe consider the cheaper calculation for middle:

middle = (stopIndex + startIndex) >> 1;

@oky1
Copy link

oky1 commented Apr 8, 2017

stopIndex = array.length - 1 not searching last index of array
first index too

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment