FAHNZ

MODE

JavaScript Binary Search Function

Coffee beansI 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.


One Response to “JavaScript Binary Search Function”

  1. [...] 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 [...]