如何对 IList执行二分查找？

Question

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

• List.BinarySearch() 不是 IList 的成员
• 没有与 ArrayList.Adapter() 方法 List< /code>
• IList 不会从 IList 继承，因此使用 ArrayList.Adapter() 是不可能的，

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

如果不可能，谁能为 IList 提供最短、最快、最智能或最漂亮的二分搜索实现？

更新

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

结论

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

Answer 1

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

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

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

Answer 2

这是我的 Lasse 代码版本。 我发现能够使用 lambda 表达式来执行搜索非常有用。 在对象列表中搜索时，它允许仅传递用于排序的键。 使用 IComparer 的实现基本上都是从这个实现派生的。

当没有找到匹配项时，我也喜欢返回~lower。 Array.BinarySearch 做到了这一点，它允许您知道您搜索的项目应该插入到哪里以保持顺序。

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <typeparam name="TSearch">The type of the searched item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <param name="comparer">The comparer that is used to compare the value
/// with the list items.</param>
/// <returns></returns>
public static int BinarySearch<TItem, TSearch>(this IList<TItem> list,
    TSearch value, Func<TSearch, TItem, int> comparer)
{
    if (list == null)
    {
        throw new ArgumentNullException("list");
    }
    if (comparer == null)
    {
        throw new ArgumentNullException("comparer");
    }

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

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

    return ~lower;
}

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <returns></returns>
public static int BinarySearch<TItem>(this IList<TItem> list, TItem value)
{
    return BinarySearch(list, value, Comparer<TItem>.Default);
}

/// <summary>
/// Performs a binary search on the specified collection.
/// </summary>
/// <typeparam name="TItem">The type of the item.</typeparam>
/// <param name="list">The list to be searched.</param>
/// <param name="value">The value to search for.</param>
/// <param name="comparer">The comparer that is used to compare the value
/// with the list items.</param>
/// <returns></returns>
public static int BinarySearch<TItem>(this IList<TItem> list, TItem value,
    IComparer<TItem> comparer)
{
    return list.BinarySearch(value, comparer.Compare);
}

Answer 3

我喜欢使用扩展方法的解决方案。 然而，有一点警告是有必要的。

这实际上是 Jon Bentley 在他的《Programming Pearls》一书中的实现，它受到了数字溢出错误的影响，该错误在大约 20 年里未被发现。 如果 IList 中有大量项目，(upper+lower) 可能会溢出 Int32。 解决这个问题的方法是使用减法稍微不同地进行中间计算； 中 = 下 + (上 - 下) / 2;

Bentley 还在《Programming Pearls》中警告说，虽然二分搜索算法于 1946 年发布，但第一个正确的实现直到 1962 年才发布。

http://en.wikipedia.org/wiki/Binary_search#Numerical_difficulties

Answer 4

一段时间以来，我一直在努力解决这个问题。 特别是 MSDN 中指定的边缘情况的返回值： http://msdn .microsoft.com/en-us/library/w4e7fxsh.aspx

我现在从 .NET 4.0 复制了 ArraySortHelper.InternalBinarySearch() 并出于各种原因制作了自己的风格。

用法：

var numbers = new List<int>() { ... };
var items = new List<FooInt>() { ... };

int result1 = numbers.BinarySearchIndexOf(5);
int result2 = items.BinarySearchIndexOfBy(foo => foo.bar, 5);

这应该适用于所有 .NET 类型。 到目前为止我已经尝试过 int、long 和 double 了。

实现：

public static class BinarySearchUtils
{
    public static int BinarySearchIndexOf<TItem>(this IList<TItem> list,
        TItem targetValue, IComparer<TItem> comparer = null)
    {
        Func<TItem, TItem, int> compareFunc =
            comparer != null ? comparer.Compare :
            (Func<TItem, TItem, int>) Comparer<TItem>.Default.Compare;
        int index = BinarySearchIndexOfBy(list, compareFunc, targetValue);
        return index;
    }

    public static int BinarySearchIndexOfBy<TItem, TValue>(this IList<TItem> list,
        Func<TItem, TValue, int> comparer, TValue value)
    {
        if (list == null)
            throw new ArgumentNullException("list");

        if (comparer == null)
            throw new ArgumentNullException("comparer");

        if (list.Count == 0)
            return -1;

        // Implementation below copied largely from .NET4
        // ArraySortHelper.InternalBinarySearch()
        int lo = 0;
        int hi = list.Count - 1;
        while (lo <= hi)
        {
            int i = lo + ((hi - lo) >> 1);
            int order = comparer(list[i], value);

            if (order == 0)
                return i;
            if (order < 0)
            {
                lo = i + 1;
            }
            else
            {
                hi = i - 1;
            }
        }

        return ~lo;
    }
}

单元测试：

[TestFixture]
public class BinarySearchUtilsTest
{
    [Test]
    public void BinarySearchReturnValueByMsdnSpecification()
    {
        var numbers = new List<int>() { 1, 3 };

        // Following the MSDN documentation for List<T>.BinarySearch:
        // http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

        // The zero-based index of item in the sorted List(Of T), if item is found;
        int index = numbers.BinarySearchIndexOf(1);
        Assert.AreEqual(0, index);

        index = numbers.BinarySearchIndexOf(3);
        Assert.AreEqual(1, index);


        // otherwise, a negative number that is the bitwise complement of the
        // index of the next element that is larger than item
        index = numbers.BinarySearchIndexOf(0);
        Assert.AreEqual(~0, index);

        index = numbers.BinarySearchIndexOf(2);
        Assert.AreEqual(~1, index);


        // or, if there is no larger element, the bitwise complement of Count.
        index = numbers.BinarySearchIndexOf(4);
        Assert.AreEqual(~numbers.Count, index);
    }
}

我刚刚从我自己的代码中删除了它，所以如果它不能开箱即用，请发表评论。

希望这能够一劳永逸地解决问题，至少根据 MSDN 规范。

Answer 5

对 IList 进行二进制搜索时，您将遇到几个问题，首先，就像您提到的那样，List上的 BinarySearch 方法是可行的。 不是 IList 接口的成员。 其次，您无法在搜索之前对列表进行排序（您必须这样做才能使二分搜索起作用）。

我认为最好的选择是创建一个新的 List，对其进行排序，然后进行搜索。 它并不完美，但如果您有 IList，您就不必有太多选择。

Answer 6

请注意，Antoine 在下面提供的实现中存在一个错误：搜索大于列表中任何项目的项目时。 返回值应该是 ~lower 而不是 ~middle。 反编译方法ArraySortHelper.InternalBinarySearch（mscorlib）以查看框架实现。

Answer 7

您可以使用List.BinarySearch(T item)。 如果您想使用自定义比较器，请使用 List.BinarySearch(T item, IComparerComparer)。 查看此 MSDN 链接更多细节。

Answer 8

如果您需要在 IList 上实现二分搜索的现成实现，Wintellect 的强大功能集合 有一个（在 <代码>Algorithms.cs）：

/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// by the natural ordering of the type (it's implementation of IComparable<T>).
/// </summary>
/// <param name="list">The sorted list to search.</param>
/// <param name="item">The item to search for.</param>
/// <param name="index">Returns the first index at which the item can be found. If the return
/// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
/// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
/// order of the list.</param>
/// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
public static int BinarySearch<T>(IList<T> list, T item, out int index)
        where T: IComparable<T>
{
    // ...
}

Answer 9

请记住，对于某些列表实现来说，二分搜索可能效率很低。 例如，对于链表，如果你正确实现它，它是 O(n) ，如果你简单地实现它，它是 O(n log n) 。

Answer 10

如果您可以使用 .NET 3.5，则可以使用 Linq 扩展方法中的构建：

using System.Linq;

IList<string> ls = ...;
var orderedList = ls.OrderBy(x => x).ToList();
orderedList.BinarySearch(...);

但是，这实际上只是 Andrew Hare 解决方案的一种稍微不同的方式，并且只有在您多次搜索同一内容时才真正有用。有序列表。

Answer 11

请注意，虽然 List 和 IList 没有 BinarySearch 方法，但 SortedList 有。