Underscore - Finden Sie aus einem sortierten Array von Objekten

Question

Underscore bietet die Funktion sortBy, um ein Array von Objekten zu sortieren. Wenn ich dieses sortierte Array jedoch einmal habe, gibt es eine Möglichkeit, ein Element mithilfe der binären Suche zu finden? Die Funktion find nutzt nicht die Tatsache, dass das Array sortiert ist, während die Funktion indexOf dies tut, aber es bietet keine Möglichkeit, den Sortierschlüssel anzugeben.

1. Fehle ich etwas?
2. Gibt es noch eine andere JS-Bibliothek, die dies ermöglicht?

Answer 1

Die Funktion _.sortedIndex wird für eine binäre Suche verwendet, ist aber etwas allgemeiner als Ihr Zweck. Ich würde es nur eine sortedFind bauen verwenden, um zum Beispiel:

_.sortedFind = function sortedFind(list, item, key) { 
    return (_.isEqual(item, list[_.sortedIndex(list, item, key)])); 
} 

Verwendungsbeispiel:

// http://jsfiddle.net/w3hzrehy/ 
_.sortedFind([10, 20, 30, 40, 50], 10); // true 

var stooges = [{name: 'moe', age: 40}, {name: 'curly', age: 60}]; 
_.sortedFind(stooges, {name: 'larry', age: 50}, 'age'); // false 
_.sortedFind(stooges, {name: 'curly', age: 60}, 'age'); // true 

Answer 2

Sie nichts fehlen. Es ist irgendwie überraschend, nicht wahr?

Google Closure Bibliothek tut Support-Funktionen innerhalb von binarysearch (Ich bin sicher, es gibt andere):

http://docs.closure-library.googlecode.com/git/namespace_goog_array.html

Sie würden es verwenden, wie Sie sich vorstellen würde:

var myArray = getPetArray(); 
goog.array.binarySearch(myArray, 'fido', function(pet) { return pet.name; }); 

Wenn Sie nicht noch eine andere Bibliothek ziehen möchten, ist die Quelle kurz und verfügbar:

http://docs.closure-library.googlecode.com/git/local_closure_goog_array_array.js.source.html#line989

Ich schneide und den wichtigen Teil hier bei Links Änderung einfügen - nur nicht vergessen, Kredit zu Google geben:

goog.array.binarySearch = function(arr, target, opt_compareFn) { 
    return goog.array.binarySearch_(arr, 
    opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */, 
    target); 
}; 

goog.array.binarySearch_ = function(arr, compareFn, isEvaluator, opt_target, 
opt_selfObj) { 
    var left = 0; // inclusive 
    var right = arr.length; // exclusive 
    var found; 
    while (left < right) { 
    var middle = (left + right) >> 1; 
    var compareResult; 
    if (isEvaluator) { 
     compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr); 
    } else { 
     compareResult = compareFn(opt_target, arr[middle]); 
    } 
    if (compareResult > 0) { 
     left = middle + 1; 
    } else { 
     right = middle; 
     // We are looking for the lowest index so we can't return immediately. 
     found = !compareResult; 
    } 
    } 
    // left is the index if found, or the insertion point otherwise. 
    // ~left is a shorthand for -left - 1. 
    return found ? left : ~left; 
}; 

goog.array.defaultCompare = function(a, b) { 
    return a > b ? 1 : a < b ? -1 : 0; 
};