Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A binary search implementation over a sorted array in JavaScript
'use strict';
// Log our sorted array to the console
console.log(myArr);
/**
* Binary search algorithm
* @param {Array} arr The array containing the item.
* @param {int} key The value to search for.
* @return {int} The index of the value if in the array or -1 if not found.
*/
function binarySearch(arr, key) {
var startIndex = 0;
var stopIndex = arr.length - 1;
var index = (startIndex + stopIndex) >> 1;
while(arr[index] != key && startIndex < stopIndex){
if (key < arr[index]) {
stopIndex = index - 1;
} else if (key > arr[index]) {
startIndex = index + 1;
}
index = (startIndex + stopIndex) >> 1;
}
if (arr[index] == key) {
return index;
} else {
console.log(key + ' not found!');
return -1;
}
}
// Create the array
var myArr = [];
/**
* Populate Array
* @return {Array} myArr a sorted array containing 100 random values
*/
function populateArray() {
/**
* Generate a random integer
* @param {variant} min The value at the bottom of our range.
* @param {variant} max The value at the top of our range.
* @return {int} A randomly generated value between the parameters
*/
function generateRandomInteger(min, max) {
return Math.floor(Math.random() * (max - min) + min);
}
// Populate the array
for (var i = 0; i <= 100; i++) {
myArr.push(generateRandomInteger(0,100));
}
// Sort the array
myArr.sort(function(a, b) {
return a - b;
})
}
populateArray();
/**
* Generate a random integer
* @return {string} Test the performance over 100 iterations
*/
function test() {
var t0 = performance.now();
// Perform the binary search on our sorted array
for (var i = 0; i <= 100; i++) {
binarySearch(myArr, i);
}
var t1 = performance.now();
return 'binarySearch performed in ' + ((t1 - t0) / 100).toFixed(4) + ' milliseconds'
}
// Run the test
test();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.