Underscore - Trova da una matrice ordinata di oggetti

Question

Underscore fornisce la funzione sortBy per ordinare una matrice di oggetti. Tuttavia, una volta che ho questo array ordinato, c'è un modo per trovare un elemento usando la ricerca binaria? La funzione find non fa leva sul fatto che l'array è ordinato, mentre la funzione indexOf lo fa, ma non fornisce un modo per specificare la chiave di ordinamento.

1. Mi manca qualcosa?
2. C'è qualche altra libreria JS che consente di farlo facilmente?

Answer 1

La funzione _.sortedIndex viene utilizzata per una ricerca binaria, ma è un po 'più generica del proprio scopo. Vorrei solo usarlo per costruire una sortedFind, ad esempio:

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

Esempio di utilizzo:

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

Non manca nulla. È un po 'sorprendente, no?

biblioteca

Google Chiusura fa le funzioni di supporto all'interno di binarySearch (sono sicuro che ci sono altri):

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

si dovrebbe utilizzare, proprio come ci si immagina:

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

Se non vuoi trascinare in un'altra libreria, la fonte è breve e disponibile:

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

taglio e incollo la parte importante nel caso in cui collega il cambiamento - basta ricordarsi di dare credito a 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; 
};