How to perform a binary search on IList?

by

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.

More Related Contents:

  1. Performance of Arrays vs. Lists
  2. Array versus List: When to use which?
  3. ArrayList vs List in C#
  4. HashSet vs. List performance
  5. Using the field of an object as a generic Dictionary key
  6. How do arrays in C# partially implement IList?
  7. Using related data stored in a 2 dimensional array
  8. Does .NET have a way to check if List a contains all items in List b?
  9. What is the difference between List (of T) and Collection(of T)?
  10. What is the difference between HashSet and List?
  11. How to initialize a List to a given size (as opposed to capacity)?
  12. .NET List Concat vs AddRange
  13. Generic List – moving an item within the list
  14. Does a List guarantee that items will be returned in the order they were added?
  15. What are alternatives to generic collections for COM Interop?
  16. Which is faster: clear collection or instantiate new
  17. Determine if a generic param is a Nullable type
  18. How does a generic constraint prevent boxing of a value type with an implicitly implemented interface?
  19. Serializing a list of Key/Value pairs to XML
  20. Concatenate strings instead of using a stack of TextBlocks
  21. How to store images using Entity Framework Code First CTP 5?
  22. Using a proxy with .NET 4.5 HttpClient
  23. Getting parent class’ name using Reflection
  24. WCF Disable Deserialization Order Sensitivity
  25. Custom button captions in .NET messagebox?
  26. How to return a page of results from SQL?
  27. Validate data using DataAnnotations with WPF & Entity Framework?
  28. In .net, how do I choose between a Decimal and a Double
  29. Do I need to dispose of a Task?
  30. What exactly is “interface based programming”?

Leave a Comment