## JavaScript Binary Search Function

I was looking into binary search functions lately and decided to comment this JavaScript binary search function I found (original is at http://www.dweebd.com/javascript/binary-search-an-array-in-javascript/) to help ensure that I had a good grasp on everything that was going on in it. Thought it might be useful for others, so I expanded my comments (read: commented the holy hell out of it) for posting here. Enjoy!

<script type="text/javascript"> // Custom sort comparator function sortNumericAscending(a, b) { return a - b; } // Based off of http://www.dweebd.com/javascript/binary-search-an-array-in-javascript/ // Extend the array object to include a new function to perform a binary search. // Since a binary search requires the array to be sorted, we can optionally // pass in the name of the function to do the comparison as well as the value to find. Array.prototype.binarySearch = function binarySearch(valueToFind, comparator) { var // The lower bound of the array, initally set to the true lower bound. lowerBound = 0, // The upper bound of the array, initally set to the true upper bound. upperBound = this.length - 1, // Stores the median index of the array. medianIndex, // Stores the result after we compare the value to find // with the value at the current median index of the array. comparisonResult; // As the loop progresses, the lower and upper bounds // will halve upon each iteration and eventually meet. while (lowerBound <= upperBound) { // Determine and store the median index. medianIndex = parseInt((lowerBound + upperBound) / 2, 10); // Check to see if a comparator was passed in. if (comparator == null) { // If there was no comparator to use, then use the default comparator. if (this[medianIndex] == valueToFind) { // If the comparison shows that the value that's at the current median index of the array // is equal to the value to find then set the comparison result to zero. comparisonResult = 0; } else { // If the comparison shows that the value that's at the current median index of the array // is less than the value to find then set the comparison result to one. If the comparison // shows that the median array value is greater than the value to find, then set the // comparison result to negative one. comparisonResult = (this[medianIndex] < valueToFind) ? 1 : -1; } } else { // If a comparator was supplied, then use it to determine // if the value is greater, lesser, or equal to the value to find. // It is presumed that this comparator is the same that was used to sort the array comparisonResult = comparator(this[medianIndex], valueToFind); } // If the comparison shows that the value that's at the current median index of the array // is less than the value to find then we know we'll need to look at the top half of this array. if (comparisonResult < 0) { // Set the new lower bound to just above the current median index // so that the next pass will only look at the top half of this array. lowerBound = medianIndex + 1; // Since the comparison result did not show that the values were equal // and we've set up the new bounds of the array to search on next, // then just disregard the rest of this iteration of the loop and contine with the next iteration. continue; } // If the comparison shows that the value at the current median index of the array // is greater than the value to find then we know we'll need to look at the bottom half of this array. if (comparisonResult > 0) { // Set the new lower bound to just below the current median index // so that the next pass will only look at the bottom half of this array. upperBound = medianIndex - 1; // Since the comparison result did not show that the values were equal // and we've set up the new bounds of the array to search on next, // then just disregard the rest of this iteration of the loop and contine with the next iteration. continue; } // We can only get to this point if the comparison result was equal // so we can return the value found at the last median index of the array. return this[medianIndex]; } // If we searched the entire array and didn't locate // the value to find then just return null. return null; }; // Testing the implementation. var newArray = [0, 3, 10, 4, 1, 2]; // Default sort comparator. newArray.sort(); // default sort is alphanumeric document.write("newArray.binarySearch(3)=" + newArray.binarySearch(3)); // Custom sort comparator. newArray.sort(sortNumericAscending); document.write("newArray.binarySearch(3, sortNumericAscending)=" + newArray.binarySearch(3, sortNumericAscending)); </script>

I still think there’s a good chance I missed something so if you find anything amiss, please let me know so I can fix.

[…] This post was mentioned on Twitter by Eric Poon and Caspar Kleijne, Tony Fahnestock. Tony Fahnestock said: New Post – JavaScript Binary Search Function http://bit.ly/bqeVGs #javascript #webdev #webdesign […]