Underscore - Find from a sorted array of objects

Question

Underscore provides the function sortBy to sort an array of objects. However once I have this sorted array, is there a way to find an element using binary search? The function find does not leverage the fact that the array is sorted, while the function indexOf does, but it does not provide a way to specify the sort key.

1. Am I missing something?
2. Is there any other JS library that allows to do this easily?

Answer 1

The function _.sortedIndex is used for a binary search, but is a little more general than your purpose. I would just use it to build a sortedFind, for example:

_.sortedFind = function sortedFind(list, item, key) {
    return (_.isEqual(item, list[_.sortedIndex(list, item, key)]));
}

Example Usage:

// http://jsfiddle.net/w3hzrehy/
_.sortedFind([10, 20, 30, 40, 50], 10); // true

var stooges = [{name: 'moe', age: 40}, {name: 'curly', age: 60}];
_.sortedFind(stooges, {name: 'larry', age: 50}, 'age'); // false
_.sortedFind(stooges, {name: 'curly', age: 60}, 'age'); // true

Answer 2

You aren't missing anything. It's kind of surprising, isn't it?

Google Closure library does support functions inside of binarySearch (I'm sure there are others):

http://docs.closure-library.googlecode.com/git/namespace_goog_array.html

You would use it just like you'd imagine:

var myArray = getPetArray();
goog.array.binarySearch(myArray, 'fido', function(pet) { return pet.name; }); 

If you don't want to drag in yet another library, the source is short and available:

http://docs.closure-library.googlecode.com/git/local_closure_goog_array_array.js.source.html#line989

I cut and paste the important part here in case links change -- just remember to give credit to Google:

goog.array.binarySearch = function(arr, target, opt_compareFn) {
  return goog.array.binarySearch_(arr,
  opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */,
  target);
};

goog.array.binarySearch_ = function(arr, compareFn, isEvaluator, opt_target,
opt_selfObj) {
   var left = 0;  // inclusive
   var right = arr.length;  // exclusive
   var found;
   while (left < right) {
     var middle = (left + right) >> 1;
     var compareResult;
     if (isEvaluator) {
       compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr);
     } else {
       compareResult = compareFn(opt_target, arr[middle]);
     }
     if (compareResult > 0) {
       left = middle + 1;
     } else {
       right = middle;
       // We are looking for the lowest index so we can't return immediately.
       found = !compareResult;
     }
   }
   // left is the index if found, or the insertion point otherwise.
   // ~left is a shorthand for -left - 1.
   return found ? left : ~left;
 };

goog.array.defaultCompare = function(a, b) {
  return a > b ? 1 : a < b ? -1 : 0;
};