List<T>.BinarySearch Metodo

Definizione

Spazio dei nomi:

System.Collections.Generic

Assembly:

System.Collections.dll

Viene usato un algoritmo di ricerca binario per individuare un elemento specifico nell'oggetto List<T> ordinato o in una parte di esso.

Overload

BinarySearch(T)	Cerca un elemento nell'intero List<T> ordinato usando l'operatore di confronto predefinito e restituisce l'indice in base zero dell'elemento.
BinarySearch(T, IComparer<T>)	Cerca un elemento nell'intero List<T> ordinato usando l'operatore di confronto specificato e restituisce l'indice in base zero dell'elemento.
BinarySearch(Int32, Int32, T, IComparer<T>)	Cerca un elemento in un intervallo di elementi nell'oggetto List<T> ordinato usando l'operatore di confronto specificato e restituisce l'indice in base zero dell'elemento.

BinarySearch(T)

Origine:

List.cs

Cerca un elemento nell'intero List<T> ordinato usando l'operatore di confronto predefinito e restituisce l'indice in base zero dell'elemento.

C#

public int BinarySearch (T item);

Parametri

item

T

Oggetto da individuare. Il valore può essere null per i tipi di riferimento.

Restituisce

Int32

Indice in base zero di item nell'oggetto List<T> ordinato, se item viene trovato; in caso contrario, un numero negativo che rappresenta il complemento bit per bit dell'indice dell'elemento successivo maggiore di item o, se non è disponibile alcun elemento maggiore, il complemento bit per bit di Count.

Eccezioni

InvalidOperationException

L'operatore di confronto predefinito Default non riesce a trovare l'implementazione dell'interfaccia generica IComparable<T> o l'interfaccia IComparable per il tipo T.

Esempio

Nell'esempio seguente viene illustrato l'overload del Sort() metodo e l'overload del BinarySearch(T) metodo. Una List<T> delle stringhe viene creata e popolata con quattro stringhe, in nessun ordine specifico. L'elenco viene visualizzato, ordinato e visualizzato di nuovo.

L'overload del BinarySearch(T) metodo viene quindi usato per cercare due stringhe non presenti nell'elenco e il Insert metodo viene usato per inserirli. Il valore restituito del BinarySearch(T) metodo è negativo in ogni caso, perché le stringhe non sono presenti nell'elenco. Prendendo il complemento bit per bit (l'operatore ~ in C# e Visual C++, Xor -1 in Visual Basic) di questo numero negativo genera l'indice del primo elemento nell'elenco più grande della stringa di ricerca e l'inserimento in questa posizione mantiene l'ordine di ordinamento. La seconda stringa di ricerca è maggiore di qualsiasi elemento nell'elenco, quindi la posizione di inserimento è alla fine dell'elenco.

C#

List<string> dinosaurs = new List<string>();

dinosaurs.Add("Pachycephalosaurus");
dinosaurs.Add("Amargasaurus");
dinosaurs.Add("Mamenchisaurus");
dinosaurs.Add("Deinonychus");

Console.WriteLine("Initial list:");
Console.WriteLine();
foreach(string dinosaur in dinosaurs)
{
    Console.WriteLine(dinosaur);
}

Console.WriteLine("\nSort:");
dinosaurs.Sort();

Console.WriteLine();
foreach(string dinosaur in dinosaurs)
{
    Console.WriteLine(dinosaur);
}

Console.WriteLine("\nBinarySearch and Insert \"Coelophysis\":");
int index = dinosaurs.BinarySearch("Coelophysis");
if (index < 0)
{
    dinosaurs.Insert(~index, "Coelophysis");
}

Console.WriteLine();
foreach(string dinosaur in dinosaurs)
{
    Console.WriteLine(dinosaur);
}

Console.WriteLine("\nBinarySearch and Insert \"Tyrannosaurus\":");
index = dinosaurs.BinarySearch("Tyrannosaurus");
if (index < 0)
{
    dinosaurs.Insert(~index, "Tyrannosaurus");
}

Console.WriteLine();
foreach(string dinosaur in dinosaurs)
{
    Console.WriteLine(dinosaur);
}
/* This code example produces the following output:

Initial list:

Pachycephalosaurus
Amargasaurus
Mamenchisaurus
Deinonychus

Sort:

Amargasaurus
Deinonychus
Mamenchisaurus
Pachycephalosaurus

BinarySearch and Insert "Coelophysis":

Amargasaurus
Coelophysis
Deinonychus
Mamenchisaurus
Pachycephalosaurus

BinarySearch and Insert "Tyrannosaurus":

Amargasaurus
Coelophysis
Deinonychus
Mamenchisaurus
Pachycephalosaurus
Tyrannosaurus
*/

Commenti

Questo metodo usa il comparer Comparer<T>.Default predefinito per il tipo T per determinare l'ordine degli elementi dell'elenco. La Comparer<T>.Default proprietà verifica se il tipo T implementa l'interfaccia IComparable<T> generica e usa tale implementazione, se disponibile. In caso contrario, Comparer<T>.Default verifica se il tipo T implementa l'interfaccia IComparable . Se il tipo T non implementa alcuna interfaccia, Comparer<T>.Default genera un InvalidOperationExceptionoggetto .

L'oggetto deve essere già ordinato in base all'implementazione del comparer. In List<T> caso contrario, il risultato non è corretto.

Il confronto null con qualsiasi tipo di riferimento è consentito e non genera un'eccezione quando si usa l'interfaccia IComparable<T> generica. Quando si ordina, null viene considerato minore di qualsiasi altro oggetto.

Se contiene List<T> più di un elemento con lo stesso valore, il metodo restituisce solo una delle occorrenze e potrebbe restituire una delle occorrenze, non necessariamente la prima.

Se l'oggetto List<T> non contiene il valore specificato, il metodo restituisce un intero negativo. È possibile applicare l'operazione di complemento bit per bit (~) a questo intero negativo per ottenere l'indice del primo elemento maggiore del valore di ricerca. Quando si inserisce il valore in List<T>, questo indice deve essere usato come punto di inserimento per mantenere l'ordine di ordinamento.

Questo metodo è un'operazione O(log n), dove n è il numero di elementi nell'intervallo.

Vedi anche

• Esecuzione di operazioni sulle stringhe indipendenti dalle impostazioni cultura nelle raccolte

BinarySearch(T, IComparer<T>)

Origine:

List.cs

Cerca un elemento nell'intero List<T> ordinato usando l'operatore di confronto specificato e restituisce l'indice in base zero dell'elemento.

C#

public int BinarySearch (T item, System.Collections.Generic.IComparer<T>? comparer);

Parametri

item

T

Oggetto da individuare. Il valore può essere null per i tipi di riferimento.

comparer

IComparer<T>

Implementazione IComparer<T> da usare quando si confrontano gli elementi.

-oppure-

null per usare la proprietà Default dell'operatore di confronto predefinito.

Restituisce

Int32

Indice in base zero di item nell'oggetto List<T> ordinato, se item viene trovato; in caso contrario, un numero negativo che rappresenta il complemento bit per bit dell'indice dell'elemento successivo maggiore di item o, se non è disponibile alcun elemento maggiore, il complemento bit per bit di Count.

Eccezioni

InvalidOperationException

comparer è null e l'operatore di confronto predefinito Default non riesce a trovare l'implementazione dell'interfaccia generica IComparable<T> o l'interfaccia IComparable per il tipo T.

Esempio

Nell'esempio seguente viene illustrato l'overload del Sort(IComparer<T>) metodo e l'overload del BinarySearch(T, IComparer<T>) metodo.

L'esempio definisce un comparer alternativo per le stringhe denominate DinoCompare, che implementa l'interfaccia IComparer<string> generica (IComparer(Of String) in Visual Basic, IComparer<String^> in Visual C++). Il comparer funziona come indicato di seguito: prima, i comparand vengono testati per nulle un riferimento Null viene considerato minore di un valore null. In secondo luogo, le lunghezze delle stringhe vengono confrontate e la stringa più lunga viene considerata maggiore. In terzo luogo, se le lunghezze sono uguali, viene usato il confronto di stringhe normali.

Una List<T> delle stringhe viene creata e popolata con quattro stringhe, in nessun ordine specifico. L'elenco viene visualizzato, ordinato usando l'operatore di confronto alternativo e visualizzato di nuovo.

L'overload del BinarySearch(T, IComparer<T>) metodo viene quindi usato per cercare diverse stringhe che non si trovano nell'elenco, utilizzando l'operatore di confronto alternativo. Il Insert metodo viene usato per inserire le stringhe. Questi due metodi si trovano nella funzione denominata SearchAndInsert, insieme al codice per accettare il complemento bit per bit (l'operatore ~ in C# e Visual C++, Xor -1 in Visual Basic) del numero negativo restituito da BinarySearch(T, IComparer<T>) e usarlo come indice per inserire la nuova stringa.

C#

using System;
using System.Collections.Generic;

public class DinoComparer: IComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == null)
        {
            if (y == null)
            {
                // If x is null and y is null, they're
                // equal.
                return 0;
            }
            else
            {
                // If x is null and y is not null, y
                // is greater.
                return -1;
            }
        }
        else
        {
            // If x is not null...
            //
            if (y == null)
                // ...and y is null, x is greater.
            {
                return 1;
            }
            else
            {
                // ...and y is not null, compare the
                // lengths of the two strings.
                //
                int retval = x.Length.CompareTo(y.Length);

                if (retval != 0)
                {
                    // If the strings are not of equal length,
                    // the longer string is greater.
                    //
                    return retval;
                }
                else
                {
                    // If the strings are of equal length,
                    // sort them with ordinary string comparison.
                    //
                    return x.CompareTo(y);
                }
            }
        }
    }
}

public class Example
{
    public static void Main()
    {
        List<string> dinosaurs = new List<string>();
        dinosaurs.Add("Pachycephalosaurus");
        dinosaurs.Add("Amargasaurus");
        dinosaurs.Add("Mamenchisaurus");
        dinosaurs.Add("Deinonychus");
        Display(dinosaurs);

        DinoComparer dc = new DinoComparer();

        Console.WriteLine("\nSort with alternate comparer:");
        dinosaurs.Sort(dc);
        Display(dinosaurs);

        SearchAndInsert(dinosaurs, "Coelophysis", dc);
        Display(dinosaurs);

        SearchAndInsert(dinosaurs, "Oviraptor", dc);
        Display(dinosaurs);

        SearchAndInsert(dinosaurs, "Tyrannosaur", dc);
        Display(dinosaurs);

        SearchAndInsert(dinosaurs, null, dc);
        Display(dinosaurs);
    }

    private static void SearchAndInsert(List<string> list,
        string insert, DinoComparer dc)
    {
        Console.WriteLine("\nBinarySearch and Insert \"{0}\":", insert);

        int index = list.BinarySearch(insert, dc);

        if (index < 0)
        {
            list.Insert(~index, insert);
        }
    }

    private static void Display(List<string> list)
    {
        Console.WriteLine();
        foreach( string s in list )
        {
            Console.WriteLine(s);
        }
    }
}

/* This code example produces the following output:

Pachycephalosaurus
Amargasaurus
Mamenchisaurus
Deinonychus

Sort with alternate comparer:

Deinonychus
Amargasaurus
Mamenchisaurus
Pachycephalosaurus

BinarySearch and Insert "Coelophysis":

Coelophysis
Deinonychus
Amargasaurus
Mamenchisaurus
Pachycephalosaurus

BinarySearch and Insert "Oviraptor":

Oviraptor
Coelophysis
Deinonychus
Amargasaurus
Mamenchisaurus
Pachycephalosaurus

BinarySearch and Insert "Tyrannosaur":

Oviraptor
Coelophysis
Deinonychus
Tyrannosaur
Amargasaurus
Mamenchisaurus
Pachycephalosaurus

BinarySearch and Insert "":


Oviraptor
Coelophysis
Deinonychus
Tyrannosaur
Amargasaurus
Mamenchisaurus
Pachycephalosaurus
 */

Commenti

Il comparer personalizza il modo in cui vengono confrontati gli elementi. Ad esempio, è possibile usare un'istanza CaseInsensitiveComparer come comparer per eseguire ricerche di stringhe senza distinzione tra maiuscole e minuscole.

Se comparer viene specificato, gli elementi dell'oggetto List<T> vengono confrontati con il valore specificato usando l'implementazione specificata IComparer<T> .

Se comparer è null, il comparer Comparer<T>.Default predefinito verifica se il tipo T implementa l'interfaccia IComparable<T> generica e usa tale implementazione, se disponibile. In caso contrario, Comparer<T>.Default verifica se il tipo T implementa l'interfaccia IComparable . Se il tipo T non implementa alcuna interfaccia, Comparer<T>.Default genera InvalidOperationException.

L'oggetto deve essere già ordinato in base all'implementazione del comparer. In List<T> caso contrario, il risultato non è corretto.

Il confronto null con qualsiasi tipo di riferimento è consentito e non genera un'eccezione quando si usa l'interfaccia IComparable<T> generica. Quando si ordina, null viene considerato minore di qualsiasi altro oggetto.

Se contiene List<T> più di un elemento con lo stesso valore, il metodo restituisce solo una delle occorrenze e potrebbe restituire una delle occorrenze, non necessariamente la prima.

Se l'oggetto List<T> non contiene il valore specificato, il metodo restituisce un intero negativo. È possibile applicare l'operazione di complemento bit per bit (~) a questo intero negativo per ottenere l'indice del primo elemento maggiore del valore di ricerca. Quando si inserisce il valore in List<T>, questo indice deve essere usato come punto di inserimento per mantenere l'ordine di ordinamento.

Questo metodo è un'operazione O(log n), dove n è il numero di elementi nell'intervallo.

Vedi anche

• Esecuzione di operazioni sulle stringhe indipendenti dalle impostazioni cultura nelle raccolte

BinarySearch(Int32, Int32, T, IComparer<T>)

Origine:

List.cs

Cerca un elemento in un intervallo di elementi nell'oggetto List<T> ordinato usando l'operatore di confronto specificato e restituisce l'indice in base zero dell'elemento.

C#

public int BinarySearch (int index, int count, T item, System.Collections.Generic.IComparer<T>? comparer);

Parametri

index

Int32

Indice iniziale in base zero dell'intervallo in cui eseguire la ricerca.

count

Int32

Lunghezza dell'intervallo in cui eseguire la ricerca.

item

T

Oggetto da individuare. Il valore può essere null per i tipi di riferimento.

comparer

IComparer<T>

Implementazione IComparer<T> da usare durante il confronto di elementi oppure null per usare la proprietà Default dell'operatore di confronto.

Restituisce

Int32

Indice in base zero di item nell'oggetto List<T> ordinato, se item viene trovato; in caso contrario, un numero negativo che rappresenta il complemento bit per bit dell'indice dell'elemento successivo maggiore di item o, se non è disponibile alcun elemento maggiore, il complemento bit per bit di Count.

Eccezioni

ArgumentOutOfRangeException

index è minore di 0.

-oppure-

count è minore di 0.

ArgumentException

index e count non indicano un intervallo valido nell'oggetto List<T>.

InvalidOperationException

comparer è null e l'operatore di confronto predefinito Default non riesce a trovare l'implementazione dell'interfaccia generica IComparable<T> o l'interfaccia IComparable per il tipo T.

Esempio

Nell'esempio seguente viene illustrato l'overload del Sort(Int32, Int32, IComparer<T>) metodo e l'overload del BinarySearch(Int32, Int32, T, IComparer<T>) metodo.

L'esempio definisce un comparer alternativo per le stringhe denominate DinoCompare, che implementa l'interfaccia IComparer<string> generica (IComparer(Of String) in Visual Basic, IComparer<String^> in Visual C++). Il comparer funziona come indicato di seguito: prima, i comparand vengono testati per nulle un riferimento Null viene considerato minore di un valore null. In secondo luogo, le lunghezze delle stringhe vengono confrontate e la stringa più lunga viene considerata maggiore. In terzo luogo, se le lunghezze sono uguali, viene usato il confronto di stringhe normali.

Una List<T> di stringhe viene creata e popolata con i nomi di cinque dinosauri erbivori e tre dinosauri carnivori. All'interno di ognuno dei due gruppi, i nomi non sono in alcun ordine di ordinamento specifico. L'elenco viene visualizzato, l'intervallo di erbivori viene ordinato usando il comparer alternativo e viene visualizzato di nuovo l'elenco.

L'overload BinarySearch(Int32, Int32, T, IComparer<T>) del metodo viene quindi usato per cercare solo l'intervallo di erbivori per "Brachiosaurus". La stringa non viene trovata e il complemento bit per bit (l'operatore ~ in C# e Visual C++, Xor -1 in Visual Basic) del numero negativo restituito dal BinarySearch(Int32, Int32, T, IComparer<T>) metodo viene usato come indice per inserire la nuova stringa.

C#

using System;
using System.Collections.Generic;

public class DinoComparer: IComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == null)
        {
            if (y == null)
            {
                // If x is null and y is null, they're
                // equal.
                return 0;
            }
            else
            {
                // If x is null and y is not null, y
                // is greater.
                return -1;
            }
        }
        else
        {
            // If x is not null...
            //
            if (y == null)
                // ...and y is null, x is greater.
            {
                return 1;
            }
            else
            {
                // ...and y is not null, compare the
                // lengths of the two strings.
                //
                int retval = x.Length.CompareTo(y.Length);

                if (retval != 0)
                {
                    // If the strings are not of equal length,
                    // the longer string is greater.
                    //
                    return retval;
                }
                else
                {
                    // If the strings are of equal length,
                    // sort them with ordinary string comparison.
                    //
                    return x.CompareTo(y);
                }
            }
        }
    }
}

public class Example
{
    public static void Main()
    {
        List<string> dinosaurs = new List<string>();

        dinosaurs.Add("Pachycephalosaurus");
        dinosaurs.Add("Parasauralophus");
        dinosaurs.Add("Amargasaurus");
        dinosaurs.Add("Galimimus");
        dinosaurs.Add("Mamenchisaurus");
        dinosaurs.Add("Deinonychus");
        dinosaurs.Add("Oviraptor");
        dinosaurs.Add("Tyrannosaurus");

        int herbivores = 5;
        Display(dinosaurs);

        DinoComparer dc = new DinoComparer();

        Console.WriteLine("\nSort a range with the alternate comparer:");
        dinosaurs.Sort(0, herbivores, dc);
        Display(dinosaurs);

        Console.WriteLine("\nBinarySearch a range and Insert \"{0}\":",
            "Brachiosaurus");

        int index = dinosaurs.BinarySearch(0, herbivores, "Brachiosaurus", dc);

        if (index < 0)
        {
            dinosaurs.Insert(~index, "Brachiosaurus");
            herbivores++;
        }

        Display(dinosaurs);
    }

    private static void Display(List<string> list)
    {
        Console.WriteLine();
        foreach( string s in list )
        {
            Console.WriteLine(s);
        }
    }
}

/* This code example produces the following output:

Pachycephalosaurus
Parasauralophus
Amargasaurus
Galimimus
Mamenchisaurus
Deinonychus
Oviraptor
Tyrannosaurus

Sort a range with the alternate comparer:

Galimimus
Amargasaurus
Mamenchisaurus
Parasauralophus
Pachycephalosaurus
Deinonychus
Oviraptor
Tyrannosaurus

BinarySearch a range and Insert "Brachiosaurus":

Galimimus
Amargasaurus
Brachiosaurus
Mamenchisaurus
Parasauralophus
Pachycephalosaurus
Deinonychus
Oviraptor
Tyrannosaurus
 */

Commenti

Il comparer personalizza il modo in cui vengono confrontati gli elementi. Ad esempio, è possibile usare un'istanza CaseInsensitiveComparer come comparer per eseguire ricerche di stringhe senza distinzione tra maiuscole e minuscole.

Se comparer viene specificato, gli elementi dell'oggetto List<T> vengono confrontati con il valore specificato usando l'implementazione specificata IComparer<T> .

Se comparer è null, il comparer Comparer<T>.Default predefinito verifica se il tipo T implementa l'interfaccia IComparable<T> generica e usa tale implementazione, se disponibile. In caso contrario, Comparer<T>.Default verifica se il tipo T implementa l'interfaccia IComparable . Se il tipo T non implementa alcuna interfaccia, Comparer<T>.Default genera InvalidOperationException.

L'oggetto deve essere già ordinato in base all'implementazione del comparer. In List<T> caso contrario, il risultato non è corretto.

Il confronto null con qualsiasi tipo di riferimento è consentito e non genera un'eccezione quando si usa l'interfaccia IComparable<T> generica. Quando si ordina, null viene considerato minore di qualsiasi altro oggetto.

Se contiene List<T> più di un elemento con lo stesso valore, il metodo restituisce solo una delle occorrenze e potrebbe restituire una delle occorrenze, non necessariamente la prima.

Se l'oggetto List<T> non contiene il valore specificato, il metodo restituisce un intero negativo. È possibile applicare l'operazione di complemento bit per bit (~) a questo intero negativo per ottenere l'indice del primo elemento maggiore del valore di ricerca. Quando si inserisce il valore in List<T>, questo indice deve essere usato come punto di inserimento per mantenere l'ordine di ordinamento.

Questo metodo è un'operazione O(log n), dove n è il numero di elementi nell'intervallo.

Vedi anche

• IComparer<T>
• IComparable<T>
• Esecuzione di operazioni sulle stringhe indipendenti dalle impostazioni cultura nelle raccolte