Binary search on a list based on a property of the list type

Question

I have a list of T, and the list is pre-sorted based off of some int index ID. I'd like to see if there's an element with an ID in it, so binary search is the quickest way.

Problem is I don't want to compare based on T, I want to compare based on the ID property.

Because the list is huge and it is at a slightly performance sensitive part of the application, applying some major transformation to the entire list would be out of the question (like selecting for obj.ID). It would be better to do the O(lg n) search and transform the items as the binary search continues doing it's job.

I tried getting a lambda to work by doing something like

// T = the List<T> type
// I = the type for transforming T -> I (as in I would be `int` in this example)
internal class BinarySearchHelper<T, I> : IComparer<I>
{
    private readonly Func<T, I> _transformer;
    private readonly Func<I, I, int> _comparer;

    public BinarySearchHelper(Func<T, I> transformFunc, Func<I, I, int> comparerFunc)
    {
        _transformer = transformFunc;
        _comparer = comparerFunc;
    }

    public int Compare(I x, I y) => _comparer(_transformer(x), _transformer(y));
}

but then I found out the hard way that List<T>.BinarySearch() operates off of the list type T, and not the type of the property that I want, so that is out because I want to search by ID (which is an int and not T).

I cannot find any standalone functions that do generic binary search, does one exist in the standard library (or even some common library I can add via nuget) that I can use? Or do I have to roll my own? Not that I mind rolling my own because the algorithm is trivial, but I like it when I don't write something that probably has been done elsewhere and is already unit tested. I don't know if I'm just missing one somewhere in some util class in the .NET ecosystem (.NET Core though, not Framework) or if I either have to look elsewhere or roll my own.

Answer 1

You need very little for a custom comparer that solves your requirements:

public class MyComparer : Comparer<MyClass>
{
    public override int Compare(MyClass x, MyClass y) => x.Id.CompareTo(y.Id);
}

If you want a generic one you can write up a class like this:

public class LambdaComparer<TSource, TKey> : IComparer<TSource> 
    where TKey : IComparable<TKey>
{
    private readonly Func<TSource, TKey> _keySelector;

    public LambdaComparer(Func<TSource, TKey> keySelector)
    {
        if (keySelector == null)
        {
            throw new ArgumentNullException(nameof(keySelector));
        }

        _keySelector = keySelector;
    }

    public override int Compare(TSource x, TSource y)
    {
        var xKey = _keySelector(x);
        var yKey = _keySelector(y);

        if (xKey == null) 
        {
            return yKey == null ? 0 : -1;
        }

        return _keySelector(x).CompareTo(_keySelector(y));
    }
}

And then wrap it up in an extension method for convenience:

public static class ListExtensions
{
    public static int BinarySearch<TSource, TKey>(
        this List<TSource> list,
        TSource item, 
        Func<TSource, TKey> keySelector) where TKey : IComparable<TKey> => 
        list.BinarySearch(item, new LambdaComparer<TSource, TKey>(keySelector));

}

Finally a test:

var list = new[]
{
    "AVeryLongString",
    null,
    "NotLong",
    "A",
    "ZZZ"
};

var orderedByDefault = list.OrderBy(s => s).ToList();
var orderedByLength = list.OrderBy(s => s?.Length).ToList();

var indexOfZZZByDefault = orderedByDefault.BinarySearch("ZZZ");
var indexOfZZZByLength = orderedByLength.BinarySearch(
    "ZZZ", 
    s => s?.Length ?? 0);

Assert.Equal(4, indexOfZZZByDefault);
Assert.Equal(2, indexOfZZZByLength);