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文档中遗漏了什么？是否有内置的更符合惯用法的方法来实现这个？或者我应该采用我的额外检查方法？

- Andrew Schwartz

---

我认为你没有从文档中漏掉任何内容，而且我也没有找到比你写的更有效的惯用方式。 - DevShep

Answer 1

浏览lodash代码，发现它有一对函数可以搜索最小的插入元素的索引，同时保持数组排序 - sortedIndex和sortedIndexBy。前者接受一个数组和一个值，后者还接受iteratee - 一个函数，用于每个元素的调用。请注意，还有sortedLastIndex和sortedLastIndexBy。这些函数寻找插入值的最后一个索引。

关于检查元素是否在数组中并在其存在时返回其索引，没有一个接受iteratee的函数，只有一个孤独的sortedIndexOf。很自然会想到有一个sortedIndexOfBy（命名开始变得棘手），以接受iteratee，以及sortedLastIndexOfBy。

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

你的额外检查解决方案现在非常好，并利用了二进制搜索优化，而不会增加太多额外的代码。

将来，当lodash包括sortedFindBy时，您总是可以将您的代码替换为新的函数调用。

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

你不会看到你的代码性能上的任何区别。

- Ivan Vashchenko

Answer 2

我已经考虑过了。我既不使用lodash也不使用underscore，但是下面的纯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) {
   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);

你可以在这里玩耍和修改它 这里。

- Redu

Answer 3

在调用 sortedIndexBy 时，value 参数应该具有时间戳属性。

从这一行开始：

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

将value替换为{ timestamp: value}

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

- Normand Roy