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 ite开发者_开发技巧m 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?

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

Do you think it is possible to use a Linq style search with BinarySearch without making a dummy T item first?
Not in it's current form. You could use a wrapper that would create the dummy T for you, it would only work for specific Ts, though (with parameterless constructors, etc.).

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.