How to perform a binary search on 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<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

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.

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

UPDATE

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>?

CONCLUSION

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.

回答1:

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.

回答2:

I like the solution with the extension method. However, a bit of warning is in order.

This is effectively Jon Bentley's implementation from his book Programming Pearls and it suffers modestly from a bug with numeric overflow that went undiscovered for 20 years or so. The (upper+lower) can overflow Int32 if you have a large number of items in the IList. A resolution to this is to do the middle calculation a bit differently using a subtraction instead; Middle = Lower + (Upper - Lower) / 2;

Bentley also warned in Programming Pearls that while the binary search algorithm was published in 1946 and the first correct implementation wasn't published until 1962.

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

回答3:

Here's my version of Lasse's code. I find it useful to be able to use a lambda expression to perform the search. When searching in a list of objects, it permits to pass only the key that was used to sort. Implementations that use IComparer are trivially derived from this one.

I also like to return ~lower when no match is found. Array.BinarySearch does it and it allows you to know where the item you searched for should be inserted in order to keep the ordering.

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

回答4:

You are going to have a couple of problems binary-searching an IList<T>, First ,like you mentioned, the BinarySearch method on the List<T> is not a member of the IList<T> interface. Second, you have no way of sorting the list prior to searching (which you must do for a binary search to work).

I think your best bet is to create a new List<T>, sort it, and then search. It's not perfect but you don't have to many options if you have an IList<T>.

回答5:

I have been struggling with getting this right for some time now. In particular the return values for edge cases as specified in MSDN: http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

I have now copied the ArraySortHelper.InternalBinarySearch() from .NET 4.0 and made my own flavor for various reasons.

Usage:

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

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

This should work with all .NET types. I have tried int, long and double so far.

Implementation:

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

Unit tests:

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

I just scissored this out from my own code, so please comment if it doesn't work out of the box.

Hope this settles the issue with a working implementation once and for all, at least according to MSDN specs.

回答6:

Note that there is a bug in the implementation provided by Antoine below: when searching for an item greater than any in the list. The return value should be ~lower not ~middle. Decompile method ArraySortHelper.InternalBinarySearch (mscorlib) to see the framework implementation.

回答7:

If you need a ready-made implementation for binary search on IList<T>s, Wintellect's Power Collections has one (in 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&lt;T&gt;).
/// </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>
{
    // ...
}

回答8:

You can use List<T>.BinarySearch(T item). If you want to use a custom comparer then use List<T>.BinarySearch(T item, IComparer<T> comparer). Take a look at this MSDN link for more details.

回答9:

Keep in mind that binary search can be quite inefficient for some list implementations. For example, for a linked list it is O(n) if you implement it correctly, and O(n log n) if you implement it naively.

回答10:

If you can use .NET 3.5, you can use the build in Linq extension methods:

using System.Linq;

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

However, this is really just a slightly different way of going about Andrew Hare's solution, and is only really helpful if you are searching multiple times off of the same ordered list.

回答11:

Note that while List and IList do not have a BinarySearch method, SortedList does.