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

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.

Answer 2

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