Ricerca binaria di un elenco C# utilizzando la condizione di delegato

Question

Ho un List<T> che desidero cercare non per un determinato articolo ma per un articolo che soddisfa una determinata condizione. Dato un elemento nell'elenco posso test che di 4 condizioni è vero:

• la voce desiderata deve essere quello di sinistra
• la voce desiderata deve essere quello di destra
• questa è la voce desiderata
• il desiderato non può essere nella lista

un rapido sguardo alle funzioni di elenco non è stato incoraggiante quindi mi chiedo se qualcuno sa fuori una funzione posso usare?

Edit: questa è una lista temporanea locale così ho saputo che verranno ordinati in modo corretto

Edit: BinarySearch sembra quasi giusto, ma nel mio caso non ho una voce da confrontare con. Userei la soluzione di Jon Skeet e ignorerei un arg, ma non sono sicuro di poter contare sul fatto che sia sempre lo stesso argomento.

Answer 1

Nuova modifica: Lascerò le ricerche binarie aggiuntive di seguito, in quanto saranno utili per gli altri, ed ecco un'opzione finale che è ciò che penso in realtà. Il tuo delegato dovrebbe restituire un numero positivo se l'elemento che sta cercando è "minore di" quello specificato, un numero negativo se è "maggiore di" quello specificato e 0 se è giusto.

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

Vecchio edit: Lascio la risposta originale al di sotto, ma qui ci sono altre due opzioni.

Il primo prende una proiezione dai dati di origine a un tipo di chiave e specifica la chiave da trovare. Il confronto si è solo fatto in modo predefinito per quel tipo di chiave:

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

Il secondo prende un Func, invece, per confrontare un elemento dalla lista con la chiave che stiamo cercando. Il codice è quasi esattamente la stessa, ovviamente - è solo il confronto che cambia:

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

Questi sono entrambi non testato, ma fare almeno compilare :)

risposta originale:

È possibile utilizzare List<T>.BinarySearch con un IComparer<T>.Non è necessario scrivere la propria implementazione di IComparer<T> - I've got on in MiscUtil che crea undelegato. Ciò indica solo le prime tre condizioni, ma la ricerca binaria risolverà l'ultima dal resto.

In effetti, il codice è così breve che potrei anche incollarlo qui (sans commenti, ammetto).

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

Così si potrebbe fare qualcosa di simile:

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

MiscUtil ha anche un ProjectionComparer potreste essere interessati a - basta specificare una proiezione, proprio come in OrderBy con LINQ - ma in realtà dipende il tuo caso d'uso.

Answer 2

Sei sicuro di queste condizioni? Normalmente questo funziona se l'elenco è ordinato, nel qual caso forse si desidera utilizzare uno SortedList<TKey, TValue> in primo luogo.

In entrambi i casi, supponendo C# 3.0 o successivo, è probabile che si desideri il metodo .Where(). Scrivi nelle tue condizioni come Lambda e lascia che il framework faccia la ricerca. Dovrebbe utilizzare una tecnica di ricerca appropriata per la raccolta.

Answer 3

Si potrebbe desiderare di implementarlo in un comparatore personalizzato per il proprio oggetto (stranamente chiamato comparatore in documenti C#).