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.

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

Curious: what are you doing that a binary search makes the difference between tractable and unacceptable? How large is your array and what are you doing to it? — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Sep 21, 2014 at 21:06
A binary search must be performed on a sorted array. Since you have an array of objects, you will most likely need a custom solution. — Ryan
– Ryan, Commented Sep 21, 2014 at 21:40
The array itself is about 1000 items, but I need to find items in it many times. So a linear search of this array in a loop may not be very efficient. — Naresh
– Naresh, Commented Sep 22, 2014 at 1:35

lossleader · Accepted Answer · 2014-09-21 22:44:03Z

5

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

edited Sep 21, 2014 at 22:44

answered Sep 21, 2014 at 21:33

lossleader

13.6k2 gold badges34 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Naresh Over a year ago

Thanks. This is very close! I actually wanted to find the index given a value. So _.sortedFind(stooges, {name: 'curly'}, 'name'); should return the index 1. I believe _.sortedIndex(stooges, {name: 'curly'}, 'name'); does exactly that although I am not sending it the full item. All I need to do is to check whether the returned index indeed contains the item with name 'curly'. The underscore docs are not very clear on this, but I think this is how it is supposed to work. Can you please confirm?

lossleader Over a year ago

@Naresh yes it looks like you are using sortedIndex correctly, if you are going to reuse your function, you may want to generalize it for function based and pure value sorts: jsfiddle.net/w3hzrehy/18 (note I had to upgrade underscore for access to the _iteratee() function.)

Michael Hays · Accepted Answer · 2014-09-21 21:40:27Z

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;
};

Thanks, this is a great solution. However @lossleader's solution was implementable with very little additional effort using underscore, hence I marked that as the accepted answer. Thanks again for your help.

Collectives™ on Stack Overflow

Underscore - Find from a sorted array of objects

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related