Binary search of a C# list using delegate condition

Question

I have a List<T> that I want to search not for a given item but for an item satisfying a given condition. Given an item in the list I can test which of 4 conditions is true:

• the desired item must be to the left
• the desired item must be to the right
• this is the desired item
• the desired can't be in the list

A quick glance at the list functions was not encouraging so I'm wondering if anyone knows off a function I can use?

Edit: this is a local temp list so I known that it will be sorted correctly

Edit: BinarySearch looks almost right but in my case I don't have an item to compare with. I'd use Jon Skeet's solution and ignore one arg, but I'm not sure that I can count on it always being the same arg.

Answer 1

New edit: I'll leave the extra binary searches below, as they'll be useful for others, and here's a final option which is I think what you actually want. Your delegate should return a positive number if the item it's looking for is "less than" the one specified, a negative number if it's "greater than" the one specified, and 0 if it's just right.

public static int BinarySearchForMatch<T>(this IList<T> list,
    Func<T,int> comparer)
{
    int min = 0;
    int max = list.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = comparer(list[mid]);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else
        {
            max = mid-1;
        }
    }
    return ~min;
}

Old edit: I'll leave the original answer below, but here are two other options.

The first takes a projection from the source data to a key type, and specifies the key to find. The comparison itself is just done in the default way for that key type:

public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list, 
    Func<TSource,TKey> projection, TKey key)
{
    int min = 0;
    int max = list.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        TKey midKey = projection(list[mid]);
        int comparison = Comparer<TKey>.Default.Compare(midKey, key);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else
        {
            max = mid-1;
        }
    }
    return ~min;
}

The second takes a Func instead, to compare an item from the list with the key we're looking for. The code is almost exactly the same, of course - it's just the comparison which changes:

public static int BinarySearchBy<TSource,TKey>(this IList<TSource> list, 
    Func<TSource,TKey,int> comparer, TKey key)
{
    int min = 0;
    int max = list.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = comparer(list[mid], key);
        if (comparison == 0)
        {
            return mid;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else
        {
            max = mid-1;
        }
    }
    return ~min;
}

These are both untested, but do at least compile :)

Original answer:

You can use List<T>.BinarySearch with an IComparer<T>. You don't have to write your own implementation of IComparer<T> - I've got on in MiscUtil which builds an IComparer<T> from a Comparison<T> delegate. That only spots the first three conditions, but the binary search will work out the last one from the rest.

In fact, the code is so short I might as well paste it here (sans comments, admittedly).

public sealed class ComparisonComparer<T> : IComparer<T>
{
    readonly Comparison<T> comparison;

    public ComparisonComparer(Comparison<T> comparison)
    {
        if (comparison == null)
        {
            throw new ArgumentNullException("comparison");
        }
        this.comparison = comparison;
    }

    public int Compare(T x, T y)
    {
        return comparison(x, y);
    }
}

So you might do something like:

var comparer = new ComparisonComparer<Person>((p1, p2) => p1.ID.CompareTo(p2.ID));
int index = list.BinarySearch(employee, comparer);

MiscUtil also has a ProjectionComparer you might be interested in - you just specify a projection, just like in OrderBy with LINQ - but it really depends on your use case.

Answer 2

Are you sure of those conditions? Normally that works if the list is sorted, in which case perhaps you want to use a SortedList<TKey, TValue> in the first place.

Either way, assuming C# 3.0 or later you probably want the .Where() method. Write in your condition as a Lambda and let the framework do the search. It should use a search technique appropriate to the collection.

Answer 3

You might want to implement it in a custom comparator for your object (strangely called comparer in C# docs).