Peut LINQ utiliser les binaires de recherche lorsque la collection est ordonnée?

Autant que je sache, il n'est pas possible avec les méthodes intégrées. Cependant, il serait relativement facile d'écrire une méthode d'extension qui vous permettra d'écrire quelque chose comme ça :

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

(en supposant, bien sûr, que vous collection met en œuvre IList ; il n'y a aucun moyen d'effectuer une recherche binaire si vous ne pouvez pas accéder aux éléments de façon aléatoire)

Voici un exemple d'implémentation :

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");
}

(pas testé... quelques ajustements pourraient être nécessaires) testé et corrigé 😉

Le fait qu'il jette un InvalidOperationException peut sembler étrange, mais c'est ce que Enumerable.First ne quand il n'y a aucun élément correspondant.

Bien, vous pouvez écrire votre propre méthode d'extension de plus de ObservableCollection<T> - mais alors, qui sera utilisé pour tout ObservableCollection<T> où votre méthode d'extension est disponible, sans savoir si c'est triée ou non.

Il faudrait aussi indiquer dans le prédicat de ce que vous vouliez trouver - qui serait le mieux fait avec une arborescence d'expression... mais que serait une douleur à analyser. Fondamentalement, la signature de First n'est pas vraiment adapté pour une recherche binaire.

Je vous suggère de ne pas essayer de surcharger le existant signatures, mais en écrire un nouveau, par exemple

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

(Je ne vais pas à la mettre en œuvre dès maintenant, mais je peux le faire plus tard si vous le souhaitez.)

En fournissant une fonction, vous pouvez effectuer une recherche par la propriété de la collection est classée par la, plutôt que par les éléments eux-mêmes.

Garder à l'esprit que tous les(? au moins la plupart) de l'extension des méthodes utilisées par LINQ sont mis en œuvre sur IQueryable<T>ouIEnumerable<T> ou IOrderedEnumerable<T> ou IOrderedQueryable<T>.

Aucun de ces interfaces prend en charge l'accès aléatoire, et, par conséquent, aucun d'entre eux peut être utilisé pour une recherche binaire. L'un des avantages de quelque chose comme LINQ, c'est que vous pouvez travailler avec de grands ensembles de données sans avoir à retourner l'ensemble du jeu de données à partir de la base de données. Évidemment, vous ne pouvez pas binaire de recherche quelque chose si vous n'avez même pas toutes les données encore.

Mais comme d'autres l'ont dit, il n'ya aucune raison vous ne pouvez pas écrire de cette méthode d'extension pour IList<T> ou d'autres types de collection qui prennent en charge l'accès aléatoire.