javascript / lodash binary search by function

Question

For most such operations, we're using the lodash library. I'm open to other suggestions, but would likely just write the function myself before importing a new lib.

lodash has sortedIndexOf, which performs a binary search in a sorted array (returns index of match or -1 if not found). It also has sortedIndexBy, which, using a binary search, finds the index to insert a new element where you can specify a function to use to do the sort comparison (returns a valid index if not found)

I cannot find a function to do a find (return index only if found) using an efficient sorted search allowing you to specify the sort value function. It might look something like this:

_.sortedFindBy(array, value, function(x){x.timestamp})

I believe I could use

var idx = _.sortedIndexBy(array, value, function(x){x.timestamp})
return (array[idx] && array[idx].timestamp === value.timestamp) ? idx : -1

but it just seems odd to me to not have the syntactically more compact and intuitive form of an already feature-rich set of sorted search functions.

Am I missing something from the lodash docs? Is there a built in way to do this more idiomatically? Or should I go with my extra-check method?

Augustus

I don't think you're missing anything from the docs, and there isn't an idiomatic way that I could find that was more efficient than what you wrote. – Baribaric

Answer 1

Reading through lodash code, looks like it has a pair of functions to search for a minimum index to insert an element while keeping array sorted - sortedIndex and sortedIndexBy. Former takes an array and a value, latter also accepts iteratee - a function, that is invoked for each element. Note, there are also sortedLastIndex and sortedLastIndexBy. Those look for the last index at which to insert a value.

When it comes to checking whether element is in the array and returning its index when it is, there's no function that accepts an iteratee, just a lonely sortedIndexOf. It would be only logical to have sortedIndexOfBy (the naming starts to get tricky here), to accept an iteratee, as well as sortedLastIndexOfBy.

I like your idea of naming it sortedFindBy and will try to implement it along with sortedLastFindBy and add a pull request to lodash.

Your extra-check solution is perfectly fine for now and takes advantage of the binary search optimization while not adding too much of extra code.

In the future, when sortedFindBy is included in lodash, you can always swap your code for the new function call.

_.sortedFindBy(array, value, function(x){x.timestamp})

You won't see any difference in performance of your code, however.

Complaisant

Answer 2

I gave some thought on this. I don't use neither lodash nor underscore but the following pure JS code might serve your purposes. It does a binary search on sorted items of primitives or objects. A provided callback is used to retrieve the value of the object property that the array's sorting is based upon. If the callback is not provided it will default to x => x (function(x) {return x}) and it will assume the array items are primitive type. At the moment this will do only numerical comparisons but a comparison callback can also be added.

Array.prototype.sortedFindIndex = function(val, cb = x => x) { // default callback for primitive arrays
  var deli = this.length-1,                                    // delta index
      base = 0;                                                // base to add the delta index
  while (deli > 0 && cb(this[base + deli]) != val) {
  	deli = ~~(deli/2);
  	cb(this[base + deli]) < val && (base += deli);
  }
  return cb(this[base + deli]) === val ? base + deli : -1;
};
var ara = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18],
    ina = ara.sortedFindIndex(17),
    arb = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"}],
    inb = arb.sortedFindIndex(4, o => o.a);
console.log(ina);
console.log(inb);

You can play with and modify it here

Seabrook

Answer 3

The value parameter in the call to sortedIndexBy should have a timestamp property.

From this line:

var idx = _.sortedIndexBy(array, value, function(x){x.timestamp})

Replace value by { timestamp: value}

var idx = _.sortedIndexBy(array, { timestamp: value} , function(x){x.timestamp})

Discolor