按功能的javascript/lodash二进制搜索

对于大多数此类操作，我们使用的是lodash库。我接受其他建议，但可能只是在导入新的lib之前自己编写函数。按功能的javascript/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文档中的内容？有没有一种内建的方式可以更通俗地做到这一点？还是应该使用我的额外支票方法？

来源

2016-06-08 Andrew Schwartz

，我不认为你错过了从文档任何东西，没有，我能找到一个习惯的方法这比你写的更有效率。 – DevShep

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

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

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

您的额外支票解决方案对于现在来说是完全不错的，并且可以利用二进制搜索优化，同时不会增加太多额外的代码。

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

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

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

来源

2016-06-16 14:20:26

我对此有了一些想法。我既不使用lodash也不使用下划线，但下面的纯JS代码可以满足您的需求。它对已排序的基元或对象项进行二分搜索。提供的回调用于检索数组排序所基于的对象属性的值。如果没有提供回调，它将默认为x => x（function(x) {return x}），它将假定数组项是原始类型。目前，这只会进行数字比较，但也可以添加比较回调。

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) { 
 
    \t deli = ~~(deli/2); 
 
    \t 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);

你可以玩，并修改它here

来源

2016-06-17 10:43:58 Redu

按功能的javascript/lodash二进制搜索

回答

相关问题