Underline - find from a sorted array of objects

Question

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

• Did I miss something?
• Is there any other JS library that makes this easy?

Answer 1

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

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

Usage example:

 // 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 are missing nothing. This is amazing, isn't it?

The Google Closure library supports functions inside binarySearch (I'm sure there are others):

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

You would use it the way you think:

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

If you do not want to drag another library, the source will be short and accessible:

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

I cut and paste the important part here if the 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; };