Thursday, July 3, 2014

Lodash: Descending Sorted Index

The sortedIndex() function available in Lodash performs a binary search on an array to tell you where you can insert the new element in question, and maintain the sort order. Which implies, of course, that the array is already sorted. This function helps you keep it that way. The benefit to keeping and array sorted is that often, you're going to want to present the values of that array in sorted order. So you could, do it just-in-time, by sorting the array when it's about to be displayed. But this has efficiency problems.

Doing a binary search to locate the best spot for the new element isn't a cost-prohibitive computation. Especially when the trade-off means not having to sort the array over and over again. What would be nice, is if the sortedIndex() function could somehow work on arrays that are sorted in descending order. By default, the function expects the sort order to be ascending. I've had plenty of cases where a descending array is needed, and I don't want to sort, then reverse the order each time.

The sortedIndex() function excepts a callback function that performs the comparison. All we have to do is return the negative value, to get the sorted index for descending order, as this example demonstrates.

var data = [ 5, 3, 2, 1 ],
    value = 4,

index = _.sortedIndex( data, value, function( i ) {
    return -i;    

data.splice( index, 0, value );

console.log( data );