下劃線 - 從排序的對象數組中查找

Question

下劃線提供對函數sortBy進行排序的對象數組。但是，一旦我有這個排序的數組，是否有一種方法來使用二分查找找到一個元素？函數find不利用數組已排序的事實，而函數indexOf具有排序功能，但它不提供指定排序關鍵字的方法。

1. 我錯過了什麼嗎？
2. 有沒有其他的JS庫可以輕鬆地做到這一點？

Answer 1

功能_.sortedIndex用於二分查找，但比您的目的更通用一些。我只想用它來建立一個sortedFind，例如：

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

實例應用：

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

你是不是缺少什麼。這有點令人驚訝，不是嗎？

谷歌封庫做的binarySearch的內部支持功能（我敢肯定有其他人）：

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

你會使用它，就像你想象：

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

如果您不想拖入另一個圖書館，則該來源很短並且可用：

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

我砍在這裏的情況下粘貼重要組成部分，鏈接改變 - 只是要記住將給予信貸谷歌：

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