How to use BinarySearch for List<T>

Let's start with this overload of List BinarySearch:

public int BinarySearch(T item, IComparer<T> comparer);

It is well known that the list should be sorted with the appropiate IComparer before using BinarySearch. But then: to search the list you will have to provide a T item. This is rather unexpected when one is used to searching items in the list based on properties of these items (i.e. using Linq or delegates/predicates). Because when I already have my T item I don't have to search it!

Now I was implementing C++ code in C# and saw that the C++ programmer used C++ style binary searches everywhere in his code as follows. First he made a new T item and gave this T item the properties he was looking for. Then he searched the list with it, to find the index of an item in the list with the same properties. The C++ comparer of course was adapted to these properties.

So this is a quite different way to look up items in a List. BinarySearch makes a dummy T item and searches for an index with which it can retrieve the real T item in the list. From a Linq point of view this feels unnatural.

My questions are:

Did I give a correct description of the idea behind BinarySearch?

Do you think it is possible to use a Linq style search with BinarySearch without making a dummy T item first?

c# list binary-search

Edit Report

1 Answer

Actually, there's nothing similar in LINQ, but you can build your own extensions. This example allow you to pass not a dummy item, but for instance just the property used in the original comparer:

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
                this IList<TElement> keySortedCollection,
                TKey key,
                Func<TElement, TKey> keySelector,
                IComparer<TKey> keyComparer)
{
    int begin = 0;
    int end = keySortedCollection.Count;
    while (end > begin)
    {
        int index = (begin + end) / 2;
        TElement el = keySortedCollection[index];
        TKey currElKey = keySelector(el);
        if (keyComparer.Compare(currElKey, key) >= 0)
            end = index;
        else
            begin = index + 1;
    }
    return end;
}

public static int FindFirstIndexGreaterThanOrEqualTo<TElement, TKey>(
                this IList<TElement> keySortedCollection,
                TKey key,
                Func<TElement, TKey> keySelector)
{
    return FindFirstIndexGreaterThanOrEqualTo(keySortedCollection,
                                               key,
                                               keySelector,
                                               Comparer<TKey>.Default);
}

With these methods, you can give a comparison that is a subset of the one you originally used to sort the collection.

Obviously, when you're using a subset of the original comparer, you can't be sure to find a single index. So these methods return a lowerbound of binary search.

answered 2011-02-08T09:18:39.357

How to use BinarySearch for List<T>

1 Answer

Your Answer