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

user_77507 0
Viewed 19858

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.

binary-search list interface generics .net
11 Answers

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.

user_2670

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

user_1192360

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

Andrew_Hare_342110

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.

Nathan_249540

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

Joel_Coehoorn_30430
Related