如何对 IList<T> 执行二分搜索? [英] How to perform a binary search on IList<T>?

问题描述

简单问题 - 给定 IList 如何执行二进制搜索，而无需自己编写方法，也无需将数据复制到具有内置二进制搜索支持的类型.我现在的状态如下.

Simple question - given an IList<T> how do you perform a binary search without writing the method yourself and without copying the data to a type with build-in binary search support. My current status is the following.

• List.BinarySearch() 不是 IList
的成员
• 没有等同于 ArrayList.Adapter() 方法用于 List
• IList 不继承自 IList，因此不能使用 ArrayList.Adapter()

• List<T>.BinarySearch() is not a member of IList<T>
• There is no equivalent of the ArrayList.Adapter() method for List<T>
• IList<T> does not inherit from IList, hence using ArrayList.Adapter() is not possible

我倾向于认为使用内置方法是不可能的，但我无法相信 BCL/FCL 中缺少这种基本方法.

I tend to believe that is not possible with build-in methods, but I cannot believe that such a basic method is missing from the BCL/FCL.

如果不可能，谁能给出IList的最短、最快、最智能或最漂亮的二进制搜索实现?

If it is not possible, who can give the shortest, fastest, smartest, or most beatiful binary search implementation for IList<T>?

更新

我们都知道在使用二进制搜索之前必须对列表进行排序，因此您可以假设它是.但我假设(但没有验证)它与 sort 存在相同的问题 - 你如何对 IList 进行排序?

We all know that a list must be sorted before using binary search, hence you can assume that it is. But I assume (but did not verify) it is the same problem with sort - how do you sort IList<T>?

结论

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

There seems to be no build-in binary search for IList<T>. One can use First() and OrderBy() LINQ methods to search and sort, but it will likly have a performance hit. Implementing it yourself (as an extension method) seems the best you can do.

推荐答案

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

I doubt there is a general purpose binary search method in .NET like that, except for the one being present in some base classes (but apparently not in the interfaces), so here's my general purpose one.

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

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

This of course assumes that the list in question is already sorted, according to the same rules that the comparer will use.

这篇关于如何对 IList<T> 执行二分搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！