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.

Solution 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.

Solution 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.

Solution 3

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

Comments

[Tjkoopa]

As there is no key (the value is the key) SortedList would be Award.

[Tjkoopa]

The code to do that is about the same as the code to do the full search my self.

[Jon Skeet]

Where does a linear scan - it can't know what you're looking for vs any current sort order.

[Tjkoopa]

Code re: Lambda (I've never even /looked/ at LINQ.)

[Jon Skeet]

@BCS: You really should. It's lovely :)

[Tjkoopa]

I like your newest answer. I think there is a typo in it T <-> TSource

[Nathan Ridley]

Hey Jon could you explain why you're returning ~min at the end of the method? I'm not quite sure what the significance of flipping the bits is in this case.

[Jon Skeet]

@NathanRidley: The BinarySearch method in List etc is designed to return the index of the element if it's present, or the bitwise inverse of the index where it would be inserted otherwise. See the docs for List<T>.BinarySearch for more details :)