Early on in my IT career, I noticed while performing searches on sorted arrays that their performance fluctuated wildly. On values that were near the start of the list, the search function was lightning fast. However, searching for values positioned closer to the end of the list would take much longer. No surprise, considering that loops always go from the start of the array to the end. I knew that there had to be a better way. That’s when I invented the binary search algorithm. Yes, it’s true. Don’t bother looking it up. I was standing on the toilet to hang a clock when I suddenly slipped and bumped my head. Even though it was 1955, I remember it like it was yesterday. In any event, regardless of who actually came up with it, the binary search algorithm is just the thing for searching through a long list of sorted items. As we’ll see today, it’s a little harder to code for strings, but thanks to the efforts of some intrepid developers, we have many good implementations to choose from. In today’s tutorial, I’ll describe two that I found that are well suited to a variety of applications.
The Demo
All of the code we’ll be looking at here is part of a demo that may be downloaded at the end of the article. The source array is in a file called “movies.js”. It contains a list of films from the Sakila sample database. It’s a MySQL database themed around the film industry that contains tables for actors, film studios, video rental stores, and the like. I enjoy using it because the data is based on real-world people, places, and things, but with the words rearranged in colorful ways. For instance, anyone up for a viewing of “BETRAYED REAR”?
var movies = [ "ACADEMY DINOSAUR", "ACE GOLDFINGER", "ADAPTATION HOLES", "AFFAIR PREJUDICE", /... "BENEATH RUSH", "BERETS AGENT", "BETRAYED REAR", "BEVERLY OUTLAW", "BIKINI BORROWERS", //... "YENTL IDAHO", "YOUNG LANGUAGE", "YOUTH KICK", "ZHIVAGO CORE", "ZOOLANDER FICTION", "ZORRO ARK" ];
You’ll also notice that items are sorted and in uppercase.
A Generic Binary Search in JavaScript
Every language has numerous variations on the Binary Search Algorithm, JavaScript included. Nicholas C. Zakas, for example, has crafted an excellent interpretation for JavaScript, which he describes on NCZOnline:
/**
* Copyright 2009 Nicholas C. Zakas. All rights reserved.
* MIT-Licensed
* Uses a binary search algorithm to locate a value in the specified array.
* @param {Array} items The array containing the item.
* @param {variant} value The value to search for.
* @return {int} The zero-based index of the value in the array or -1 if not found.
*/
function binarySearch(items, value){
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex)/2);
while(items[middle] != value && startIndex < stopIndex){
//adjust search area
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}
//recalculate middle
middle = Math.floor((stopIndex + startIndex)/2);
}
//make sure it's the right value
return (items[middle] != value) ? -1 : middle;
}
It works with both numbers and strings, but does not support partial or case-insensitive string matching.
To use it, simply pass in the array and search string. Invoking it with a search string of “BIKINI BORROWERS” results in the following:
var index = binarySearch(movies, "BIKINI BORROWERS"); //returns 69
A Binary Search for Strings
Of the countless variations of the Binary Search Algorithm, many are tailored to string matching. One that caught my eye was written by Cedric Dugas. In his article, Optimizing search functionality with large JavaScript arrays, he discusses his searchBinary() function. It accepts an extra “case insensitive?” boolean argument and matches partial strings, returning an array, making it an excellent companion for an autocomplete widget.
To use it, simply reference the searchBinary.js file in your page. Here’s my test page:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html; charset=utf-8" />
<title>JavaScript String Binary Search Demo</title>
<script src="movies.js" type="text/javascript" charset="utf-8"></script>
<script src="searchNormal.js" type="text/javascript" charset="utf-8"></script>
<script src="searchBinary.js" type="text/javascript" charset="utf-8"></script>
</head>
<body>
<h1>JavaScript String Binary Search Demo</h1>
<p>Results are printed to the console. Press F12 to open the developer console and then refresh the page.</p>
<script type="text/javascript">
testBinary = searchBinary("BIKINI", movies, false);
console.log('searchBinary("BIKINI", movies, false) = [' + testBinary + ']');
testBinary = searchBinary("b", movies, false);
console.log('searchBinary("b", movies, false) = [' + testBinary + ']');
testBinary = searchBinary("b", movies, true);
console.log('searchBinary("b", movies, true) = [' + testBinary + ']');
</script>
</body>
</html>
This archive file contains all the files you’ll need to run the demo. Be sure to open your JavaScript console to view the results as they are printed using console.log().
Conclusion
When efficiency counts, don’t take the amateur approach of iterating over large sorted data sets using a straight for loop. Find a binary search function that suits your purpose and use it!
