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

.net, binary-search, generics, interface, list

Solution

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.

Problem

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.

Original source