The following is an implementation of a binary search for arrays which gives you the ability to do fuzzy matches (default), exact matches, or specify your own comparison function:
(function() { // Use this if the search isn't called with a 2nd param or it // is false. function fnFuzzy(a, b) { return a < b ? -1 : a > b ? 1 : a == b ? 0 : null; } // Use this if the search is called with a 2nd param of true. function fnExact(a, b) { return a < b ? -1 : a > b ? 1 : a === b ? 0 : null; } // Recursively does a binary search. function binarySearch(arr, item, min, max, fnCmp) { if(min > max) { return -1; } var mid = parseInt((min + max) / 2); var ret = fnCmp(item, arr[mid]); if(ret) { return binarySearch(arr, item, ret > 0 ? mid + 1 : min, ret < 0 ? mid - 1 : max, fnCmp); } else if(ret == 0) { return mid; } } // Define the prototypal function. Array.prototype.binarySearch = function(item, extactMatch) { return binarySearch(this, item, 0, this.length - 1, extactMatch ? typeof extactMatch == "function" ? extactMatch : fnExact : fnFuzzy); }; })();
I used the following to test the normal execution of this binary function:
// Create a pre-sorted array of distinct random numbers ranging // from 0 to 9999 and keep a reverse index to validate what is // being returned by the binarySearch() function: var arr = [], reverseIndex = {"-1" : -1}; for(var limit = 10000, i = 0; i < limit; i++) { if(Math.random() < 0.5) { reverseIndex[i] = arr.length; arr.push(i); } else { reverseIndex[i] = -1; } } reverseIndex[limit] = -1; // Run through all numbers from -1 to 10000, using the reverse // index making sure that the binarySearch() function works // properly: for(var v1, v2, i = -1; i <= limit; i++) { // If the binary search doesn't return the correct thing, // let the user know. if((v1 = arr.binarySearch(i)) != (v2 = reverseIndex[i])) { alert("The search for " + i + " returned an index of " + v1 + " when it should have returned " + v2 + "."); break; } } // If all of the tests were successfully run, tell the user. if(i == limit + 1) { alert("All " + arr.length + " numbers that should have been found were found."); }