.net - 如何对 IList 执行二分查找？

Question

简单问题 - 给出 IList<T>如何在不自己编写方法且不将数据复制到具有内置二分搜索支持的类型的情况下执行二分搜索。我目前的状态如下。

• List<T>.BinarySearch()不是 IList<T> 的成员
• 没有与 ArrayList.Adapter() 等效的项方法List<T>
• IList<T>不继承自IList ，因此使用 ArrayList.Adapter()不可能的

我倾向于认为使用内置方法不可能做到这一点，但我无法相信 BCL/FCL 中缺少这样的基本方法。

如果不可能，谁能给 IList<T> 最短、最快、最智能、最漂亮的二分查找实现？

更新

我们都知道在使用二分搜索之前必须对列表进行排序，因此您可以假设它是这样的。但我假设(但没有验证)排序有同样的问题 - 你如何排序 IList<T> ？

结论

似乎没有内置的二分搜索 IList<T> 。可以使用First()和OrderBy() LINQ 方法进行搜索和排序，但它可能会影响性能。自己实现它(作为扩展方法)似乎是您能做的最好的事情。

Answer 1

我怀疑 .NET 中是否存在这样的通用二分搜索方法，除了某些基类中存在的方法(但显然不在接口(interface)中)，所以这是我的通用二分搜索方法。

public static Int32 BinarySearchIndexOf<T>(this IList<T> list, T value, IComparer<T> comparer = null)
{
    if (list == null)
        throw new ArgumentNullException(nameof(list));

    comparer = comparer ?? Comparer<T>.Default;

    Int32 lower = 0;
    Int32 upper = list.Count - 1;

    while (lower <= upper)
    {
        Int32 middle = lower + (upper - lower) / 2;
        Int32 comparisonResult = comparer.Compare(value, list[middle]);
        if (comparisonResult == 0)
            return middle;
        else if (comparisonResult < 0)
            upper = middle - 1;
        else
            lower = middle + 1;
    }

    return ~lower;
}

这当然假设相关列表已经根据比较器将使用的相同规则进行排序。