Can LINQ use binary search when the collection is ordered?

Question

Can I somehow "instruct" LINQ to use binary search when the collection that I'm trying to search is ordered. I'm using an ObservableCollection<T>, populated with ordered data, and I'm trying to use Enumerable.First(<Predicate>). In my predicate, I'm filtering by the value of the field my collection's sorted by.

Solution 1

As far as I know, it's not possible with the built-in methods. However it would be relatively easy to write an extension method that would allow you to write something like that :

var item = myCollection.BinarySearch(i => i.Id, 42);

(assuming, of course, that you collection implements IList ; there's no way to perform a binary search if you can't access the items randomly)

Here's a sample implementation :

public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
        where TKey : IComparable<TKey>
{
    if (list.Count == 0)
        throw new InvalidOperationException("Item not found");

    int min = 0;
    int max = list.Count;
    while (min < max)
    {
        int mid = min + ((max - min) / 2);
        T midItem = list[mid];
        TKey midKey = keySelector(midItem);
        int comp = midKey.CompareTo(key);
        if (comp < 0)
        {
            min = mid + 1;
        }
        else if (comp > 0)
        {
            max = mid - 1;
        }
        else
        {
            return midItem;
        }
    }
    if (min == max &&
        min < list.Count &&
        keySelector(list[min]).CompareTo(key) == 0)
    {
        return list[min];
    }
    throw new InvalidOperationException("Item not found");
}

(not tested... a few adjustments might be necessary) Now tested and fixed ;)

The fact that it throws an InvalidOperationException may seem strange, but that's what Enumerable.First does when there's no matching item.

Solution 2

The accepted answer is very good.

However, I need that the BinarySearch returns the index of the first item that is larger, as the List<T>.BinarySearch() does.

So I watched its implementation by using ILSpy, then I modified it to have a selector parameter. I hope it will be as useful to someone as it is for me:

public static class ListExtensions
{
    public static int BinarySearch<T, U>(this IList<T> tf, U target, Func<T, U> selector)
    {
        var lo = 0;
        var hi = (int)tf.Count - 1;
        var comp = Comparer<U>.Default;

        while (lo <= hi)
        {
            var median = lo + (hi - lo >> 1);
            var num = comp.Compare(selector(tf[median]), target);
            if (num == 0)
                return median;
            if (num < 0)
                lo = median + 1;
            else
                hi = median - 1;
        }

        return ~lo;
    }
}

Solution 3

Well, you can write your own extension method over ObservableCollection<T> - but then that will be used for any ObservableCollection<T> where your extension method is available, without knowing whether it's sorted or not.

You'd also have to indicate in the predicate what you wanted to find - which would be better done with an expression tree... but that would be a pain to parse. Basically, the signature of First isn't really suitable for a binary search.

I suggest you don't try to overload the existing signatures, but write a new one, e.g.

public static TElement BinarySearch<TElement, TKey>
    (this IList<TElement> collection, Func<TElement, TItem> keySelector,
     TKey key)

(I'm not going to implement it right now, but I can do so later if you want.)

By providing a function, you can search by the property the collection is sorted by, rather than by the items themselves.

Solution 4

Keep in mind that all(? at least most) of the extension methods used by LINQ are implemented on IQueryable<T>orIEnumerable<T> or IOrderedEnumerable<T> or IOrderedQueryable<T>.

None of these interfaces supports random access, and therefore none of them can be used for a binary search. One of the benefits of something like LINQ is that you can work with large datasets without having to return the entire dataset from the database. Obviously you can't binary search something if you don't even have all of the data yet.

But as others have said, there is no reason at all you can't write this extension method for IList<T> or other collection types that support random access.

Solution 5

Enumerable.First(predicate) works on an IEnumarable<T> which only supports enumeration, therefore it does not have random access to the items within.

Also, your predicate contains arbitrary code that eventually results in true or false, and so cannot indicate whether the tested item was too low or too high. This information would be needed in order to do a binary search.

Enumerable.First(predicate) can only test each item in order as it walks through the enumeration.

View more solutions

Comments

[Thomas Levesque]

Hi, I just found and fixed a bug in my implementation, in case you're using it...

[Crouching Kitten]

That's not median, but mean.

[Ben Voigt]

@CrouchingKitten: The center index is the index of the median.

[Crouching Kitten]

@BenVoigt ah yes, I didn't think about that.

[Gabe Halsmer]

Excellent implementation which informs you of all the "between spots".