LINQ可以在订购集合时使用二进制搜索吗？
我可以以某种方式“指示”LINQ在我尝试搜索的集合被订购时使用二进制搜索。 我正在使用ObservableCollection ，填充有序数据，我正在尝试使用Enumerable.First（） 。 在我的谓词中，我按照我的集合排序的字段的值进行过滤。
据我所知，使用内置方法是不可能的。 但是编写一个允许你编写类似的扩展方法会相对容易：
var item = myCollection.BinarySearch(i => i.Id, 42);
（当然，假设您的集合实现了IList;如果您无法随机访问项目，则无法执行二进制搜索）
这是一个示例实现：
public static T BinarySearch(this IList list, Func keySelector, TKey key) where TKey : IComparable { if (list.Count == 0) throw new InvalidOperationException("Item not found"); int min = 0; int max = list.Count; while (min < max) { int mid = min + ((max - min) / 2); T midItem = list[mid]; TKey midKey = keySelector(midItem); int comp = midKey.CompareTo(key); if (comp < 0) { min = mid + 1; } else if (comp > 0) { max = mid - 1; } else { return midItem; } } if (min == max && min < list.Count && keySelector(list[min]).CompareTo(key) == 0) { return list[min]; } throw new InvalidOperationException("Item not found"); }
（未经测试......可能需要进行一些调整）现已测试并修复;）
抛出InvalidOperationException这一事实可能看起来很奇怪，但这就是Enumerable.First在没有匹配项时所做的事情。
接受的答案非常好。
但是，我需要BinarySearch返回较大的第一个项的索引，如List所做的那样。
所以我通过使用ILSpy观察了它的实现，然后我将其修改为具有选择器参数。 我希望它对某人有用，对我来说也是如此：
public static class ListExtensions { public static int BinarySearch(this IList tf, U target, Func selector) { var lo = 0; var hi = (int)tf.Count - 1; var comp = Comparer.Default; while (lo <= hi) { var median = lo + (hi - lo >> 1); var num = comp.Compare(selector(tf[median]), target); if (num == 0) return median; if (num < 0) lo = median + 1; else hi = median - 1; } return ~lo; } }
好吧，你可以在ObservableCollection编写自己的扩展方法 – 但是这将用于你的扩展方法可用的任何 ObservableCollection ，而不知道它是否已经排序。
你还必须在谓词中指出你想要找到的东西 – 用表达式树做得更好……但是解析起来会很麻烦。 基本上， First的签名并不适合二进制搜索。
我建议你不要试图重写现有的签名，而是写一个新签名，例如
public static TElement BinarySearch (this IList collection, Func keySelector, TKey key)
（我现在不打算实现它，但如果你愿意，我可以稍后再这样做。）
通过提供函数，您可以按属性搜索集合，而不是按项目本身进行搜索。
Enumerable.First(predicate)在IEnumarable ，它只支持枚举，因此它没有随机访问其中的项目。
此外，您的谓词包含最终导致true或false的任意代码，因此无法指示测试项目是否太低或太高。 为了进行二分查找，需要此信息。
Enumerable.First(predicate)只能在遍历枚举时按顺序测试每个项目。
请记住，LINQ使用的所有（？至少大多数）扩展方法都是在IQueryable或IEnumerable或IOrderedEnumerable或IOrderedQueryable 。
这些接口都不支持随机访问，因此它们都不能用于二进制搜索。 LINQ之类的好处之一是您可以使用大型数据集而无需从数据库返回整个数据集。 如果你还没有所有的数据，显然你不能二进制搜索。
但正如其他人所说，没有理由你不能为IList或其他支持随机访问的集合类型编写这种扩展方法。