How to perform a binary search on IList<T>?

Question

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.

Answer 1

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

Answer 2

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 BinarySearch<T>(this IList<T> list, T value)
{
    return BinarySearch(list, value, Comparer<T>.Default);
}

public static Int32 BinarySearch<T>(this IList<T> list, T value, IComparer<T> comparer)
{
    #region Parameter Validation

    if (Object.ReferenceEquals(null, list))
        throw new ArgumentNullException("list");
    if (Object.ReferenceEquals(null, comparer))
        throw new ArgumentNullException("comparer");

    #endregion

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

    while (lower <= upper)
    {
        Int32 middle = (lower + upper) / 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 -1;
}

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

Answer 3

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

Answer 4

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

using System.Linq;

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

However, this is really just a slightly different way of going about Andrew Hare's solution.

Answer 5

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

Answer 6

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>
{
    // ...
}

Answer 7

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.

Answer 8

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 ~middle 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;

    int middle = lower;
    while (lower <= upper)
    {
        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 9

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.