Podkreślenie - Znajdź z posortowanej tablicy obiektów

Question

Podkreślenie służy do sortowania tablicy obiektów za pomocą funkcji sortBy. Jednak gdy już mam tę posortowaną tablicę, czy istnieje sposób na znalezienie elementu za pomocą wyszukiwania binarnego? Funkcja find nie wykorzystuje faktu, że tablica jest sortowana, podczas gdy funkcja działa, ale nie zapewnia sposobu na określenie klucza sortowania.

1. Czy czegoś brakuje?
2. Czy istnieje inna biblioteka JS, która pozwala to łatwo?

Answer 1

Funkcja _.sortedIndex służy do wyszukiwania binarnego, ale jest nieco bardziej ogólna niż cel. Chciałbym po prostu użyć go do budowy sortedFind, na przykład:

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

Przykład użycia:

// 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

Nie brakuje niczego. To trochę zaskakujące, prawda?

Google Closure biblioteka ma funkcje pomocnicze wewnątrz binarySearch (jestem pewien, że są inne):

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

będzie go używać tak jak chcesz sobie wyobrazić:

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

Jeśli nie chcesz przeciągać kolejnej biblioteki, źródło jest krótkie i dostępne:

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

wyciąć i wkleić tutaj ważną rolę w przypadku linki zmiany - Wystarczy pamiętać, aby dać kredyt Google:

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; 
};