按功能的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二進制搜索

回答

相關問題