javascript/lodash 二进制搜索功能

Question

对于大多数此类操作，我们使用的是 lodash 库。我对其他建议持开放态度，但可能会在导入新库之前自己编写函数。

lodash 有 sortedIndexOf，它在排序数组中执行二进制搜索(返回匹配项的索引，如果未找到则返回 -1)。它还具有 sortedIndexBy，它使用二进制搜索查找索引以插入新元素，您可以在其中指定用于进行排序比较的函数(如果未找到则返回有效索引)

我找不到使用允许您指定排序值函数的高效排序搜索来执行查找(仅在找到时返回索引)的函数。它可能看起来像这样:

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

我相信我可以用

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

但对我来说，没有已经功能丰富的已排序搜索函数集的句法上更紧凑和直观的形式似乎很奇怪。

我是否遗漏了 lodash 文档中的某些内容？有没有一种内置的方法可以更惯用地做到这一点？还是我应该使用我的额外检查方法？

Answer 1

阅读 lodash 代码，看起来它有一对函数来搜索最小索引以插入元素，同时保持数组排序 - sortedIndex 和 sortedIndexBy。前者接受一个数组和一个值，后者也接受 iteratee - 一个为每个元素调用的函数。请注意，还有 sortedLastIndex 和 sortedLastIndexBy。那些查找要插入值的最后一个索引。

当谈到检查元素是否在数组中并返回它的索引时，没有接受迭代对象的函数，只有一个孤独的 sortedIndexOf。使用 sortedIndexOfBy(这里的命名开始变得棘手)来接受迭代器以及 sortedLastIndexOfBy 是合乎逻辑的。

我喜欢你将其命名为 sortedFindBy 的想法，并将尝试将其与 sortedLastFindBy 一起实现，并向 lodash 添加拉取请求。

您的额外检查解决方案目前非常好，它利用了二进制搜索优化，同时没有添加太多额外代码。

将来，当 sortedFindBy 包含在 lodash 中时，您可以随时为新的函数调用交换代码。

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

但是，您不会看到代码的性能有任何差异。