当集合是有序的时，LINQ 可以使用二分搜索吗？

Question

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

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.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;
    }
}

Answer 3

好吧，您可以在 ObservableCollection 上编写自己的扩展方法 - 但随后该方法将用于任何 ObservableCollection扩展方法可用，而不知道它是否已排序。

您还必须在谓词中指出您想要查找的内容 - 使用表达式树会更好...但这会很难解析。基本上，First 的签名并不适合二分搜索。

我建议您不要尝试重载现有签名，而是编写一个新签名，例如

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

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

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

Answer 4

Enumerable.First(predicate) 适用于仅支持枚举的 IEnumarable，因此它无法随机访问其中的项目。

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

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

Answer 5

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

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

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