List<T>.BinarySearch Metodo

  • Riferimento

Definizione

Spazio dei nomi:
System.Collections.Generic
Assembly:
System.Collections.dll
Assembly:
mscorlib.dll
Assembly:
netstandard.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)

Source:
List.cs
Source:
List.cs
Source:
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.

public:
 int BinarySearch(T item);
public int BinarySearch (T item);
member this.BinarySearch : 'T -> int
Public Function BinarySearch (item As T) As Integer

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.

using namespace System;
using namespace System::Collections::Generic;

void main()
{
    List<String^>^ dinosaurs = gcnew List<String^>();

    dinosaurs->Add("Pachycephalosaurus");
    dinosaurs->Add("Amargasaurus");
    dinosaurs->Add("Mamenchisaurus");
    dinosaurs->Add("Deinonychus");

    Console::WriteLine();
    for each(String^ dinosaur in dinosaurs)
    {
        Console::WriteLine(dinosaur);
    }

    Console::WriteLine("\nSort");
    dinosaurs->Sort();

    Console::WriteLine();
    for each(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();
    for each(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();
    for each(String^ dinosaur in dinosaurs)
    {
        Console::WriteLine(dinosaur);
    }
}

/* This code example produces the following output:

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
 */

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
*/

Imports System.Collections.Generic

Public Class Example

    Public Shared Sub Main()

        Dim dinosaurs As New List(Of String)

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

        Console.WriteLine()
        For Each dinosaur As String In dinosaurs
            Console.WriteLine(dinosaur)
        Next

        Console.WriteLine(vbLf & "Sort")
        dinosaurs.Sort

        Console.WriteLine()
        For Each dinosaur As String In dinosaurs
            Console.WriteLine(dinosaur)
        Next

        Console.WriteLine(vbLf & _
            "BinarySearch and Insert ""Coelophysis"":")
        Dim index As Integer = dinosaurs.BinarySearch("Coelophysis")
        If index < 0 Then
            index = index Xor -1
            dinosaurs.Insert(index, "Coelophysis")
        End If

        Console.WriteLine()
        For Each dinosaur As String In dinosaurs
            Console.WriteLine(dinosaur)
        Next

        Console.WriteLine(vbLf & _
            "BinarySearch and Insert ""Tyrannosaurus"":")
        index = dinosaurs.BinarySearch("Tyrannosaurus")
        If index < 0 Then
            index = index Xor -1
            dinosaurs.Insert(index, "Tyrannosaurus")
        End If

        Console.WriteLine()
        For Each dinosaur As String In dinosaurs
            Console.WriteLine(dinosaur)
        Next

    End Sub
End Class

' This code example produces the following output:
'
'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

Si applica a

BinarySearch(T, IComparer<T>)

Source:
List.cs
Source:
List.cs
Source:
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.

public:
 int BinarySearch(T item, System::Collections::Generic::IComparer<T> ^ comparer);
public int BinarySearch (T item, System.Collections.Generic.IComparer<T> comparer);
public int BinarySearch (T item, System.Collections.Generic.IComparer<T>? comparer);
member this.BinarySearch : 'T * System.Collections.Generic.IComparer<'T> -> int
Public Function BinarySearch (item As T, comparer As IComparer(Of T)) As Integer

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.

using namespace System;
using namespace System::Collections::Generic;

public ref class DinoComparer: IComparer<String^>
{
public:
    virtual int Compare(String^ x, String^ y)
    {
        if (x == nullptr)
        {
            if (y == nullptr)
            {
                // 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 == nullptr)
                // ...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);
                }
            }
        }
    }
};

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

void Display(List<String^>^ list)
{
    Console::WriteLine();
    for each(String^ s in list)
    {
        Console::WriteLine(s);
    }
};

void main()
{
    List<String^>^ dinosaurs = gcnew List<String^>();
    dinosaurs->Add("Pachycephalosaurus");
    dinosaurs->Add("Amargasaurus");
    dinosaurs->Add("Mamenchisaurus");
    dinosaurs->Add("Deinonychus");
    Display(dinosaurs);

    DinoComparer^ dc = gcnew 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, nullptr, dc);
    Display(dinosaurs);
}

/* 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
 */

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
 */

Imports System.Collections.Generic

Public Class DinoComparer
    Implements IComparer(Of String)

    Public Function Compare(ByVal x As String, _
        ByVal y As String) As Integer _
        Implements IComparer(Of String).Compare

        If x Is Nothing Then
            If y Is Nothing Then 
                ' If x is Nothing and y is Nothing, they're
                ' equal. 
                Return 0
            Else
                ' If x is Nothing and y is not Nothing, y
                ' is greater. 
                Return -1
            End If
        Else
            ' If x is not Nothing...
            '
            If y Is Nothing Then
                ' ...and y is Nothing, x is greater.
                Return 1
            Else
                ' ...and y is not Nothing, compare the 
                ' lengths of the two strings.
                '
                Dim retval As Integer = _
                    x.Length.CompareTo(y.Length)

                If retval <> 0 Then 
                    ' 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)
                End If
            End If
        End If
    End Function
End Class

Public Class Example

    Public Shared Sub Main()

        Dim dinosaurs As New List(Of String)
        dinosaurs.Add("Pachycephalosaurus")
        dinosaurs.Add("Amargasaurus")
        dinosaurs.Add("Mamenchisaurus")
        dinosaurs.Add("Deinonychus")
        Display(dinosaurs)

        Dim dc As New DinoComparer

        Console.WriteLine(vbLf & "Sort 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, Nothing, dc)
        Display(dinosaurs)
    End Sub

    Private Shared Sub SearchAndInsert( _
        ByVal lis As List(Of String), _
        ByVal insert As String, ByVal dc As DinoComparer)

        Console.WriteLine(vbLf & _
            "BinarySearch and Insert ""{0}"":", insert)

        Dim index As Integer = lis.BinarySearch(insert, dc)

        If index < 0 Then
            index = index Xor -1
            lis.Insert(index, insert)
        End If
    End Sub

    Private Shared Sub Display(ByVal lis As List(Of String))
        Console.WriteLine()
        For Each s As String In lis
            Console.WriteLine(s)
        Next
    End Sub
End Class

' 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

Si applica a

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

Source:
List.cs
Source:
List.cs
Source:
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.

public:
 int BinarySearch(int index, int count, T item, System::Collections::Generic::IComparer<T> ^ comparer);
public int BinarySearch (int index, int count, T item, System.Collections.Generic.IComparer<T> comparer);
public int BinarySearch (int index, int count, T item, System.Collections.Generic.IComparer<T>? comparer);
member this.BinarySearch : int * int * 'T * System.Collections.Generic.IComparer<'T> -> int
Public Function BinarySearch (index As Integer, count As Integer, item As T, comparer As IComparer(Of T)) As Integer

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.

using namespace System;
using namespace System::Collections::Generic;

public ref class DinoComparer: IComparer<String^>
{
public:
    virtual int Compare(String^ x, String^ y)
    {
        if (x == nullptr)
        {
            if (y == nullptr)
            {
                // 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 == nullptr)
                // ...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);
                }
            }
        }
    }
};

void Display(List<String^>^ list)
{
    Console::WriteLine();
    for each(String^ s in list)
    {
        Console::WriteLine(s);
    }
};

void main()
{
    List<String^>^ dinosaurs = gcnew 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 = gcnew 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);
}

/* 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
 */

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
 */

Imports System.Collections.Generic

Public Class DinoComparer
    Implements IComparer(Of String)

    Public Function Compare(ByVal x As String, _
        ByVal y As String) As Integer _
        Implements IComparer(Of String).Compare

        If x Is Nothing Then
            If y Is Nothing Then 
                ' If x is Nothing and y is Nothing, they're
                ' equal. 
                Return 0
            Else
                ' If x is Nothing and y is not Nothing, y
                ' is greater. 
                Return -1
            End If
        Else
            ' If x is not Nothing...
            '
            If y Is Nothing Then
                ' ...and y is Nothing, x is greater.
                Return 1
            Else
                ' ...and y is not Nothing, compare the 
                ' lengths of the two strings.
                '
                Dim retval As Integer = _
                    x.Length.CompareTo(y.Length)

                If retval <> 0 Then 
                    ' 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)
                End If
            End If
        End If
    End Function
End Class

Public Class Example

    Public Shared Sub Main()

        Dim dinosaurs As New List(Of 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")

        Dim herbivores As Integer = 5
        Display(dinosaurs)

        Dim dc As New DinoComparer

        Console.WriteLine(vbLf & _
            "Sort a range with the alternate comparer:")
        dinosaurs.Sort(0, herbivores, dc)
        Display(dinosaurs)

        Console.WriteLine(vbLf & _
            "BinarySearch a range and Insert ""{0}"":", _
            "Brachiosaurus")

        Dim index As Integer = _
            dinosaurs.BinarySearch(0, herbivores, "Brachiosaurus", dc)

        If index < 0 Then
            index = index Xor -1
            dinosaurs.Insert(index, "Brachiosaurus")
            herbivores += 1
        End If

        Display(dinosaurs)

    End Sub

    Private Shared Sub Display(ByVal lis As List(Of String))
        Console.WriteLine()
        For Each s As String In lis
            Console.WriteLine(s)
        Next
    End Sub
End Class

' 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

Si applica a