下划线 - 从排序的对象数组中查找

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