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.");
}

Leave a Reply

Your email address will not be published. Required fields are marked *