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?

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.