Recherche binaire d'une liste C# en utilisant la condition déléguée

Question

J'ai un List<T> que je veux rechercher non pour un élément donné mais pour un élément satisfaisant une condition donnée. Étant donné un élément dans la liste que je peux tester les 4 conditions est vrai:

• l'élément souhaité doit être à la
• gauche l'élément souhaité doit être à droite
• c'est l'élément souhaité
• désiré ne peut pas être dans la liste

un coup d'œil rapide aux fonctions de la liste n'a pas été encourageante et je me demande si quelqu'un sait hors fonction que je peux utiliser?

Edit: ceci est une liste temporaire locale donc je su que ce sera réglé correctement

Edit: BinarySearch ressemble presque droit, mais dans mon cas, je ne l'ai pas un élément de comparaison. J'utiliserais la solution de Jon Skeet et j'ignorerais un argument, mais je ne suis pas sûr de pouvoir toujours compter sur le même argument.

Answer 1

Nouvelle édition: Je vais laisser les recherches binaires supplémentaires ci-dessous, car elles seront utiles pour les autres, et voici une dernière option qui est ce que vous voulez vraiment. Votre délégué doit renvoyer un nombre positif si l'élément qu'il recherche est "inférieur à" celui spécifié, un nombre négatif s'il est "supérieur à" celui spécifié, et 0 s'il est juste.

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: Je vais laisser la réponse originale ci-dessous, mais voici deux autres options.

La première prend une projection des données source vers un type de clé et spécifie la clé à rechercher. La comparaison elle-même est juste fait de la manière par défaut pour ce type de clé:

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

Le second prend place Func, pour comparer un élément de la liste avec la clé que nous recherchons. Le code est presque exactement la même chose, bien sûr - il est juste la comparaison qui change:

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

Ce sont à la fois non testé, mais faire au moins compiler :)

réponse originale:

Vous pouvez utiliser List<T>.BinarySearch avec un IComparer<T>.Vous n'avez pas besoin d'écrire votre propre implémentation de IComparer<T> - Je suis sur MiscUtil qui construit un IComparer<T> à partir d'un délégué Comparison<T>. Cela ne fait que repérer les trois premières conditions, mais la recherche binaire permettra de résoudre le dernier du reste.

En fait, le code est si court que je pourrais aussi bien le coller ici (sans commentaires, certes).

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

Alors vous pourriez faire quelque chose comme:

var comparer = new ComparisonComparer<Person>((p1, p2) => p1.ID.CompareTo(p2.ID)); 
int index = list.BinarySearch(employee, comparer); 

MiscUtil a aussi un ProjectionComparer que vous pourriez être intéressé par - vous suffit de spécifier une projection, comme dans OrderBy avec LINQ - mais cela dépend vraiment votre cas d'utilisation.

Answer 2

Etes-vous sûr de ces conditions? Normalement cela fonctionne si la liste est triée, auquel cas vous voulez peut-être utiliser un SortedList<TKey, TValue> en premier lieu. De toute façon, en supposant C# 3.0 ou plus tard, vous voulez probablement la méthode .Where(). Ecrivez dans votre condition de Lambda et laissez le cadre faire la recherche. Il devrait utiliser une technique de recherche appropriée à la collection.

Answer 3

Vous voudrez peut-être l'implémenter dans un comparateur personnalisé pour votre objet (étrangement appelé les documents en C#).