LINQ可以使用二进制搜索集合时是有序？ [英] Can LINQ use binary search when the collection is ordered?

问题描述

我可以以某种方式指示LINQ使用二进制搜索时我试图搜索的集合是有序的。我使用的是的ObservableCollection＆LT; T＆GT; ，填充了有序的数据，我试图用<一个href=\"http://msdn.microsoft.com/en-us/library/bb535050.aspx\">Enumerable.First(<$p$pdicate>).在我的predicate，我被我收藏的排序中字段的值过滤。

Can I somehow "instruct" LINQ to use binary search when the collection that I'm trying to search is ordered. I'm using an ObservableCollection<T>, populated with ordered data, and I'm trying to use Enumerable.First(<Predicate>). In my predicate, I'm filtering by the value of the field my collection's sorted by.

推荐答案

据我所知，这是不可能的内置方法。然而，它会相对容易编写扩展方法，允许你写类似的东西：

As far as I know, it's not possible with the built-in methods. However it would be relatively easy to write an extension method that would allow you to write something like that :

var item = myCollection.BinarySearch(i => i.Id, 42);

（假设，当然，前提是你收集实现IList的，没有任何办法来执行二进制搜索，如果你不能访问该项目随机）

(assuming, of course, that you collection implements IList ; there's no way to perform a binary search if you can't access the items randomly)

下面是一个示例实现：

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 确实没有当匹配的项目。

The fact that it throws an InvalidOperationException may seem strange, but that's what Enumerable.First does when there's no matching item.

这篇关于LINQ可以使用二进制搜索集合时是有序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！