I’m going to start a new blog series: Algorithms in JavaScript. This first article will discuss the implementation of “Binary Search”.
The Problem
You’ve got a huge array of sorted values and you need to find the location in that array of a particular value (or whether that value exists within the list at all.)
Brute Force (And Why It Sucks)
The simplest approach to finding the location of your target value within a sorted list of values is to iterate through the list one-by-one until you:
- find the target value (returning the location when found), or
- find a value greater-than the target value (returning
null because this means the target can’t possibly exist in the array.)
Why does it suck? Consider the case when you’re given an array containing a million elements and your target is nowhere to be found: you’ll have to look at every element in the array! In computer science parlance, this worst-case situation of having to look at every element in the array means that the algorithm is O(n) (read “Big-Oh of n”) and its run-time will increase linearly with the size of the search array.
“Binary” Searching
Instead of looking at every element in the array from lowest to highest: let’s look at the middle of the array first and if it’s greater than our target we’ll search in the first half of the array, if it’s lesser than the target we can search in the second half of the array, and if it’s equal to the target - our answer is the middle index. You keep repeating this pattern of cutting the array in half until you either find the target or run out of array (and hence: didn’t find the target).
If you’re still confused, think of it like the days before the internet when you would have to “let your fingers do the walking” to search a phone book for your friend’s number. You’d crack the book open somewhere in the middle and look at one of the names on the page. If your friend’s name comes before that name you’ll look in the chunk of pages to the left of the current page, if it comes after that name you will look in the other chunk of pages, and if it’s pretty close to the name you found at first - you’re in luck and just have to scan the current page for your friend (using binary search again!)
Because we’re repeatedly cutting our search space in half with each iteration, and we’re only evaluating the endpoints and median of the space each time we can say that Binary Search performs in O(log n) time (this series won’t deal with proving this type of thing, but you can find plenty of proofs online with a quick visit to google.) What this means is that even when searching within a million-item array, we’ll only end up iterating about twenty times at the worst case. That’s 50,000 times faster than the worst case of the brute-force situation!
Pseudocode
function search(array, target, start, end):
if start > end:
return NOT_FOUND
if array[start] is target:
return start
if array[end] is target:
return end
middle = ( start + end ) / 2
if array[middle] > target:
return search(array, target, start+1, middle)
if array[middle] < target:
return search(array, target, middle, end-1)
return middle
You would call the above function with start = 0 and end = array.length-1.
Binary Search in JavaScript
The following code is also available with a demo application on jsbin.
function binarySearch( sortedValues, target ){
// summary:
// Performs a binary search on an array of sorted
// values for a specified target.
// sortedValues: Array
// Array of values to search within.
// target: String|Number
// Item to search for, within the sortedValues array.
// returns:
// Number or null. The location of the target within
// the sortedValues array, if found. Otherwise returns
// null.
// define the recursive function.
function search( low, high ) {
// If the low index is greater than the high index,
// return null for not-found.
if ( low > high ) {
return null;
}
// If the value at the low index is our target, return
// the low index.
if ( sortedValues[low] === target ){
return low;
}
// If the value at the high index is our target, return
// the high index.
if ( sortedValues[high] === target ){
return high;
}
// Find the middle index and median element.
var middle = Math.floor( ( low + high ) / 2 );
var middleElement = sortedValues[middle];
// Recursive calls, depending on whether or not the
// middleElement is less-than or greater-than the
// target.
// Note: We can use high-1 and low+1 because we've
// already checked for equality at the high and low
// indexes above.
if ( middleElement > target ) {
return search(low+1, middle);
} else if ( middleElement < target ) {
return search(middle, high-1);
}
// If middleElement === target, we can return that value.
return middle;
}
// Start our search between the first and last elements of
// the array.
return search(0, sortedValues.length-1);
}What other algorithms would you like to see discussed and implemented with JavaScript?
