22

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

4

5 回答 5

33

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

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");
}

（未测试...可能需要进行一些调整）现已测试并修复；）

它抛出 an 的事实InvalidOperationException可能看起来很奇怪，但是Enumerable.First当没有匹配的项目时就是这样。

于 2009-11-19T20:42:40.967 回答
8

接受的答案非常好。

但是，我需要 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;
    }
}
于 2014-04-15T18:55:36.413 回答
2

好吧，您可以编写自己的扩展方法ObservableCollection<T>- 但随后将用于您的扩展方法可用的任何 ObservableCollection<T>地方，而无需知道它是否已排序。

您还必须在谓词中指出您想要查找的内容 - 最好使用表达式树来完成......但这会很痛苦。基本上，签名First并不真正适合二进制搜索。

我建议你不要试图重载现有的签名，而是写一个新的，例如

public static TElement BinarySearch<TElement, TKey>
    (this IList<TElement> collection, Func<TElement, TItem> keySelector,
     TKey key)

（我现在不打算实现它，但如果你愿意，我可以稍后再实现。）

通过提供一个函数，您可以按集合排序的属性进行搜索，而不是按项目本身进行搜索。

于 2009-11-19T20:42:56.270 回答
1

Enumerable.First(predicate)在IEnumarable<T>仅支持枚举的情况下工作，因此它不能随机访问其中的项目。

此外，您的谓词包含最终导致真或假的任意代码，因此无法指示测试项目是太低还是太高。为了进行二分搜索，需要此信息。

Enumerable.First(predicate)只能在遍历枚举时按顺序测试每个项目。

于 2009-11-19T20:42:08.753 回答
1

请记住，LINQ 使用的所有（？至少大多数）扩展方法都是在IQueryable<T>orIEnumerable<T>或IOrderedEnumerable<T>or上实现的IOrderedQueryable<T>。

这些接口都不支持随机访问，因此它们都不能用于二分搜索。LINQ 之类的好处之一是您可以处理大型数据集，而无需从数据库中返回整个数据集。显然，如果您甚至还没有所有数据，您就无法进行二进制搜索。

但正如其他人所说，完全没有理由不能为IList<T>支持随机访问的其他集合类型或其他集合类型编写此扩展方法。

于 2009-11-19T21:39:01.273 回答