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.

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

Answer 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;     } }