当我尝试搜索的集合已排序时,我能否以某种方式“指示”LINQ 使用二进制搜索?我正在使用 ObservableCollection<T>
,填充了有序数据,我正在尝试使用 Enumerable.First(<Predicate>) .在我的谓词中,我按我的集合排序所依据的字段的值进行过滤。
最佳答案
据我所知,使用内置方法是不可能的。然而,编写一个允许您编写类似内容的扩展方法会相对容易:
var item = myCollection.BinarySearch(i => i.Id, 42);
(当然,假设您的集合实现了 IList ;如果您不能随机访问项目,则无法执行二进制搜索)
这是一个示例实现:
public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
where TKey : IComparable<TKey>
{
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
在没有匹配项时所做的事情。
关于c# - LINQ 可以在集合排序时使用二分查找吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1766328/