Aug
15
2010
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.