c# - LINQ 可以在集合排序时使用二分查找吗？

Question

当我尝试搜索的集合已排序时，我能否以某种方式“指示”LINQ 使用二进制搜索？我正在使用 ObservableCollection<T> ，填充了有序数据，我正在尝试使用 Enumerable.First(<Predicate>) .在我的谓词中，我按我的集合排序所依据的字段的值进行过滤。

Answer 1

据我所知，使用内置方法是不可能的。然而，编写一个允许您编写类似内容的扩展方法会相对容易:

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 在没有匹配项时所做的事情。