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没有匹配项时的情况.

Answer 2

接受的答案非常好。

但是，我需要 BinarySearch 返回第一个较大项目的索引，就像List<T>.BinarySearch()这样。

所以我通过使用ILSpy观看了它的实现，然后我修改了它以具有选择器参数。我希望它对某人和我一样有用：

public static class ListExtensions
{
    public static int BinarySearch<T, U>(this IList<T> tf, U target, Func<T, U> selector)
    {
        var lo = 0;
        var hi = (int)tf.Count - 1;
        var comp = Comparer<U>.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;
    }
}