List<T>.BinarySearch Methode

  • Referenz

Definition

Namespace:
System.Collections.Generic
Assembly:
System.Collections.dll
Assembly:
mscorlib.dll
Assembly:
netstandard.dll

Verwendet einen binären Suchalgorithmus für die Suche nach einem bestimmten Element bzw. einen Teil dieses Elements in der sortierten List<T>.

Überlädt

BinarySearch(T)

Durchsucht mithilfe des Standardcomparers die gesamte sortierte List<T> nach einem Element und gibt den nullbasierten Index des Elements zurück.
BinarySearch(T, IComparer<T>)

Durchsucht mithilfe des angegebenen Comparers die gesamte sortierte List<T> nach einem Element und gibt den nullbasierten Index des Elements zurück.
BinarySearch(Int32, Int32, T, IComparer<T>)

Durchsucht mithilfe des angegebenen Vergleichs einen Bereich von Elementen in der sortierten List<T> nach einem Element und gibt den nullbasierten Index des Elements zurück.

BinarySearch(T)

Durchsucht mithilfe des Standardcomparers die gesamte sortierte List<T> nach einem Element und gibt den nullbasierten Index des Elements zurück.

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

Parameter

item
T

Das zu suchende Objekt. Der Wert kann für Verweistypen null sein.

Gibt zurück

Int32

Der nullbasierte Index von item in der sortierten List<T>, sofern item gefunden wird, andernfalls eine negative Zahl, die das bitweise Komplement des Indexes des nächsten Elements darstellt, das größer als item ist, oder, wenn kein größeres Element vorhanden ist, das bitweise Komplement von Count.

Ausnahmen

InvalidOperationException

Der Standardcomparer Default kann keine Implementierung der generischen IComparable<T>-Schnittstelle oder der IComparable-Schnittstelle für den Typ T finden.

Beispiele

Im folgenden Beispiel wird die Methodenüberladung und die Sort() BinarySearch(T) Methodenüberladung veranschaulicht. Eine List<T> Zeichenfolge wird erstellt und mit vier Zeichenfolgen gefüllt, in keiner bestimmten Reihenfolge. Die Liste wird angezeigt, sortiert und erneut angezeigt.

Die BinarySearch(T) Methodenüberladung wird dann verwendet, um nach zwei Zeichenfolgen zu suchen, die sich nicht in der Liste befinden, und die Insert Methode wird verwendet, um sie einzufügen. Der Rückgabewert der Methode ist in jedem Fall negativ, da sich die Zeichenfolgen nicht in der BinarySearch(T) Liste befinden. Wenn Sie das Bitzeiger-Komplement (den ~-Operator in C# und Visual C++, -1 in Visual Basic) dieser negativen Zahl verwenden, wird der Index des ersten Elements in der Liste erzeugt, Xor die größer ist als die Suchzeichenfolge, und das Einfügen an dieser Stelle behält die Sortierreihenfolge. Die zweite Suchzeichenfolge ist größer als jedes Element in der Liste, sodass die Einfügeposition am Ende der Liste liegt.

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

Hinweise

Diese Methode verwendet den Standardvergleich Comparer<T>.Default für den Typ T , um die Reihenfolge der Listenelemente zu bestimmen. Die Comparer<T>.Default Eigenschaft überprüft, ob der Typ T die IComparable<T> generische Schnittstelle implementiert und diese Implementierung verwendet, falls verfügbar. Wenn nicht, überprüft der Typ, Comparer<T>.Default ob der Typ T die IComparable Schnittstelle implementiert. Wenn der Typ T keine Schnittstelle implementiert, Comparer<T>.Default wird ein InvalidOperationException.

Dies List<T> muss bereits nach der Vergleichsimplementierung sortiert werden. Andernfalls ist das Ergebnis falsch.

Vergleich null mit jedem Referenztyp ist zulässig und generiert keine Ausnahme beim Verwenden der IComparable<T> generischen Schnittstelle. Bei der Sortierung null gilt es als kleiner als jedes andere Objekt.

Wenn das List<T> Element mehr als ein Element mit demselben Wert enthält, gibt die Methode nur einen der Vorkommen zurück, und es kann eine der Vorkommen zurückgeben, nicht unbedingt die erste.

Wenn der List<T> angegebene Wert nicht enthalten ist, gibt die Methode eine negative ganze Zahl zurück. Sie können den Bitzeiger-Ergänzungsvorgang (~) auf diese negative ganze Zahl anwenden, um den Index des ersten Elements abzurufen, das größer als der Suchwert ist. Wenn Sie den Wert in den List<T>Wert einfügen, sollte dieser Index als Einfügemarke verwendet werden, um die Sortierreihenfolge beizubehalten.

Diese Methode ist ein O(log n)-Vorgang, wobei n die Anzahl der Elemente im Bereich ist.

Siehe auch

Gilt für

BinarySearch(T, IComparer<T>)

Durchsucht mithilfe des angegebenen Comparers die gesamte sortierte List<T> nach einem Element und gibt den nullbasierten Index des Elements zurück.

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

Parameter

item
T

Das zu suchende Objekt. Der Wert kann für Verweistypen null sein.

comparer
IComparer<T>

Die IComparer<T>-Implementierung, die beim Vergleich von Elementen verwendet werden soll.

  • oder - null zur Verwendung des Standardcomparers Default.

Gibt zurück

Int32

Der nullbasierte Index von item in der sortierten List<T>, sofern item gefunden wird, andernfalls eine negative Zahl, die das bitweise Komplement des Indexes des nächsten Elements darstellt, das größer als item ist, oder, wenn kein größeres Element vorhanden ist, das bitweise Komplement von Count.

Ausnahmen

InvalidOperationException

comparer ist null, und der Standardcomparer Default kann keine Implementierung der generischen IComparable<T>-Schnittstelle oder der IComparable-Schnittstelle für den Typ T finden.

Beispiele

Im folgenden Beispiel wird die Methodenüberladung und die Sort(IComparer<T>) BinarySearch(T, IComparer<T>) Methodenüberladung veranschaulicht.

Das Beispiel definiert einen alternativen Vergleich für Zeichenfolgen namens DinoCompare, der die IComparer<string>``IComparer(Of String) generische Schnittstelle (in Visual Basic, IComparer<String^> in Visual C++) implementiert. Der Vergleich funktioniert wie folgt: Zunächst werden die Vergleiche für null, und ein Nullverweis wird als kleiner als eine Nicht-Null behandelt. Zweitens werden die Zeichenfolgenlängen verglichen, und die längere Zeichenfolge gilt als größer. Drittens, wenn die Längen gleich sind, werden normale Zeichenfolgenvergleiche verwendet.

Eine List<T> Zeichenfolge wird erstellt und mit vier Zeichenfolgen gefüllt, in keiner bestimmten Reihenfolge. Die Liste wird angezeigt, mithilfe des alternativen Vergleichs sortiert und erneut angezeigt.

Die BinarySearch(T, IComparer<T>) Methodenüberladung wird dann verwendet, um nach mehreren Zeichenfolgen zu suchen, die sich nicht in der Liste befinden und den alternativen Vergleich verwenden. Die Insert Methode wird verwendet, um die Zeichenfolgen einzufügen. Diese beiden Methoden befinden sich in der Funktion namens SearchAndInsert, zusammen mit Code, um die bitweise Ergänzung (den ~ Operator in C# und Visual C++, Xor -1 in Visual Basic) der von ihm zurückgegebenen BinarySearch(T, IComparer<T>) negativen Zahl zu übernehmen und als Index zum Einfügen der neuen Zeichenfolge zu verwenden.

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

Hinweise

Der Vergleicher passt an, wie die Elemente verglichen werden. Sie können beispielsweise eine CaseInsensitiveComparer Instanz als Vergleichsinstanz verwenden, um Groß- und Kleinschreibungszeichenfolgensuche auszuführen.

Wenn comparer angegeben, werden die Elemente der List<T> angegebenen Implementierung mit dem angegebenen IComparer<T> Wert verglichen.

nullWenn comparer es sich um einen Standardvergleich handelt, überprüft der StandardvergleichComparer<T>.Default, ob der Typ T die IComparable<T> generische Schnittstelle implementiert und diese Implementierung verwendet, falls verfügbar. Wenn nicht, überprüft der Typ, Comparer<T>.Default ob der Typ T die IComparable Schnittstelle implementiert. Wenn der Typ T keine Schnittstelle implementiert, Comparer<T>.Default wird InvalidOperationExceptionausgelöst.

Dies List<T> muss bereits nach der Vergleichsimplementierung sortiert werden. Andernfalls ist das Ergebnis falsch.

Vergleich null mit jedem Referenztyp ist zulässig und generiert keine Ausnahme beim Verwenden der IComparable<T> generischen Schnittstelle. Bei der Sortierung null gilt es als kleiner als jedes andere Objekt.

Wenn das List<T> Element mehr als ein Element mit demselben Wert enthält, gibt die Methode nur einen der Vorkommen zurück, und es kann eine der Vorkommen zurückgeben, nicht unbedingt die erste.

Wenn der List<T> angegebene Wert nicht enthalten ist, gibt die Methode eine negative ganze Zahl zurück. Sie können den Bitzeiger-Ergänzungsvorgang (~) auf diese negative ganze Zahl anwenden, um den Index des ersten Elements abzurufen, das größer als der Suchwert ist. Wenn Sie den Wert in den List<T>Wert einfügen, sollte dieser Index als Einfügemarke verwendet werden, um die Sortierreihenfolge beizubehalten.

Diese Methode ist ein O(log n)-Vorgang, wobei n die Anzahl der Elemente im Bereich ist.

Siehe auch

Gilt für

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

Durchsucht mithilfe des angegebenen Vergleichs einen Bereich von Elementen in der sortierten List<T> nach einem Element und gibt den nullbasierten Index des Elements zurück.

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

Parameter

index
Int32

Der nullbasierte Startindex des zu durchsuchenden Bereichs.

count
Int32

Die Länge des zu durchsuchenden Bereichs.

item
T

Das zu suchende Objekt. Der Wert kann für Verweistypen null sein.

comparer
IComparer<T>

Die IComparer<T>-Implementierung, die beim Vergleichen von Elementen verwendet werden soll, oder null, wenn der Standardvergleich Default verwendet werden soll.

Gibt zurück

Int32

Der nullbasierte Index von item in der sortierten List<T>, sofern item gefunden wird, andernfalls eine negative Zahl, die das bitweise Komplement des Indexes des nächsten Elements darstellt, das größer als item ist, oder, wenn kein größeres Element vorhanden ist, das bitweise Komplement von Count.

Ausnahmen

ArgumentOutOfRangeException

index ist kleiner als 0.

- oder - count ist kleiner als 0.

ArgumentException

index und count geben keinen gültigen Bereich in der List<T> an.

InvalidOperationException

comparer ist null, und der Standardcomparer Default kann keine Implementierung der generischen IComparable<T>-Schnittstelle oder der IComparable-Schnittstelle für den Typ T finden.

Beispiele

Im folgenden Beispiel wird die Sort(Int32, Int32, IComparer<T>) Methodenüberladung und die BinarySearch(Int32, Int32, T, IComparer<T>) Methodenüberladung veranschaulicht.

Im Beispiel wird ein alternativer Vergleich für Zeichenfolgen namens DinoCompare definiert, der die IComparer<string> generische Schnittstelle (IComparer(Of String) in Visual BasicIComparer<String^>, in Visual C++) implementiert. Der Vergleichser funktioniert wie folgt: Zunächst werden die Vergleiche getestet nullund ein NULL-Bezug wird als kleiner als ein Nullwert behandelt. Zweitens werden die Zeichenfolgenlängen verglichen, und die längere Zeichenfolge wird als größer betrachtet. Drittens, wenn die Längen gleich sind, wird gewöhnlicher Zeichenfolgenvergleich verwendet.

Eine List<T> Reihe von Zeichenfolgen wird erstellt und mit den Namen von fünf herbivorischen Dinosauriern und drei karnivorous Dinosauriern gefüllt. Innerhalb jeder der beiden Gruppen befinden sich die Namen nicht in einer bestimmten Sortierreihenfolge. Die Liste wird angezeigt, der Bereich der Pflanzenfresser wird mithilfe des alternativen Vergleichs sortiert, und die Liste wird erneut angezeigt.

Die BinarySearch(Int32, Int32, T, IComparer<T>) Methodenüberladung wird dann verwendet, um nur die Palette von Pflanzenfresser für "Brachiosaurus" zu durchsuchen. Die Zeichenfolge wird nicht gefunden, und die bitweise Ergänzung (der ~-Operator in C# und Visual C++, Xor -1 in Visual Basic) der negativen Zahl, die von der BinarySearch(Int32, Int32, T, IComparer<T>) Methode zurückgegeben wird, wird als Index zum Einfügen der neuen Zeichenfolge verwendet.

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

Hinweise

Der Vergleicher passt an, wie die Elemente verglichen werden. Sie können beispielsweise eine CaseInsensitiveComparer Instanz als Vergleichsinstanz verwenden, um Groß- und Kleinschreibungszeichenfolgensuche auszuführen.

Wenn comparer angegeben, werden die Elemente der List<T> angegebenen Implementierung mit dem angegebenen IComparer<T> Wert verglichen.

nullWenn comparer es sich um einen Standardvergleich handelt, überprüft der StandardvergleichComparer<T>.Default, ob der Typ T die IComparable<T> generische Schnittstelle implementiert und diese Implementierung verwendet, falls verfügbar. Wenn nicht, überprüft der Typ, Comparer<T>.Default ob der Typ T die IComparable Schnittstelle implementiert. Wenn der Typ T keine Schnittstelle implementiert, Comparer<T>.Default wird InvalidOperationExceptionausgelöst.

Dies List<T> muss bereits nach der Vergleichsimplementierung sortiert werden. Andernfalls ist das Ergebnis falsch.

Vergleich null mit jedem Referenztyp ist zulässig und generiert keine Ausnahme beim Verwenden der IComparable<T> generischen Schnittstelle. Bei der Sortierung gilt dies null als kleiner als jedes andere Objekt.

Wenn das List<T> Element mehrere Elemente mit demselben Wert enthält, gibt die Methode nur eines der Vorkommen zurück, und es kann eines der Vorkommen zurückgeben, nicht unbedingt die erste.

Wenn der List<T> angegebene Wert nicht enthalten ist, gibt die Methode eine negative ganze Zahl zurück. Sie können den bitweise Ergänzungsvorgang (~) auf diese negative ganze Zahl anwenden, um den Index des ersten Elements abzurufen, das größer als der Suchwert ist. Beim Einfügen des Werts in den List<T>Wert sollte dieser Index als Einfügemarke verwendet werden, um die Sortierreihenfolge beizubehalten.

Diese Methode ist ein O(log n)-Vorgang, wobei n die Anzahl der Elemente im Bereich ist.

Siehe auch

Gilt für