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)

Quelle:
List.cs
Quelle:
List.cs
Quelle:
List.cs

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 werden die Sort() Methodenüberladung und die BinarySearch(T) Methodenüberladung veranschaulicht. Eine List<T> von Zeichenfolgen wird erstellt und mit vier Zeichenfolgen in keiner bestimmten Reihenfolge aufgefüllt. Die Liste wird angezeigt, sortiert und erneut angezeigt.

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

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 verwendet diese Implementierung, falls verfügbar. Wenn dies nicht der Fehler ist, wird überprüft, Comparer<T>.Default ob vom Typ T die IComparable Schnittstelle implementiert wird. Wenn vom Typ T keine schnittstelle implementiert wird, Comparer<T>.Default wird eine InvalidOperationExceptionausgelöst.

Muss List<T> bereits nach der Vergleichsimplementierung sortiert werden, andernfalls ist das Ergebnis falsch.

Der Vergleich null mit einem beliebigen Verweistyp ist zulässig und generiert bei Verwendung der IComparable<T> generischen Schnittstelle keine Ausnahme. Beim Sortieren null gilt als kleiner als jedes andere Objekt.

Wenn mehr List<T> als ein Element mit demselben Wert enthält, gibt die Methode nur eines der Vorkommen zurück, und möglicherweise gibt sie eines der Vorkommen zurück, nicht unbedingt das erste.

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

Bei dieser Methode handelt es sich um einen O(log n)-Vorgang, wobei n die Anzahl der Elemente im Bereich darstellt.

Weitere Informationen

Gilt für:

BinarySearch(T, IComparer<T>)

Quelle:
List.cs
Quelle:
List.cs
Quelle:
List.cs

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 werden die Sort(IComparer<T>) Methodenüberladung und die BinarySearch(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 Basic, IComparer<String^> in Visual C++) implementiert. Der Vergleich funktioniert wie folgt: Zuerst werden die Vergleichszeichen auf nullgetestet, und ein NULL-Verweis wird als kleiner als ein ungleich NULL behandelt. Zweitens werden die Zeichenfolgenlängen verglichen, und die längere Zeichenfolge wird als größer angesehen. Drittens: Wenn die Längen gleich sind, wird ein gewöhnlicher Zeichenfolgenvergleich verwendet.

Eine List<T> von Zeichenfolgen wird erstellt und mit vier Zeichenfolgen in keiner bestimmten Reihenfolge aufgefüllt. 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 nicht in der Liste enthalten sind, wobei der alternative Vergleich verwendet wird. Die Insert -Methode wird verwendet, um die Zeichenfolgen einzufügen. Diese beiden Methoden befinden sich in der Funktion mit dem Namen SearchAndInsertzusammen mit Code, um die bitweise Ergänzung (der ~ -Operator in C# und Visual C++, Xor -1 in Visual Basic) der von zurückgegebenen BinarySearch(T, IComparer<T>) negativen Zahl zu verwenden und sie 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 Vergleich passt an, wie die Elemente verglichen werden. Sie können beispielsweise eine CaseInsensitiveComparer instance als Vergleich verwenden, um Zeichenfolgensuchen ohne Berücksichtigung der Groß-/Kleinschreibung durchzuführen.

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

Wenn comparer ist null, überprüft der Standardvergleich Comparer<T>.Default , ob der Typ T die IComparable<T> generische Schnittstelle implementiert, und verwendet diese Implementierung, sofern verfügbar. Wenn dies nicht der Fehler ist, wird überprüft, Comparer<T>.Default ob vom Typ T die IComparable Schnittstelle implementiert wird. Wenn vom Typ T keine schnittstelle implementiert wird, Comparer<T>.Default wird ausgelöst InvalidOperationException.

Muss List<T> bereits nach der Vergleichsimplementierung sortiert werden, andernfalls ist das Ergebnis falsch.

Der Vergleich null mit einem beliebigen Verweistyp ist zulässig und generiert bei Verwendung der IComparable<T> generischen Schnittstelle keine Ausnahme. Beim Sortieren null gilt als kleiner als jedes andere Objekt.

Wenn mehr List<T> als ein Element mit demselben Wert enthält, gibt die Methode nur eines der Vorkommen zurück, und möglicherweise gibt sie eines der Vorkommen zurück, nicht unbedingt das erste.

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

Bei dieser Methode handelt es sich um einen O(log n)-Vorgang, wobei n die Anzahl der Elemente im Bereich darstellt.

Weitere Informationen

Gilt für:

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

Quelle:
List.cs
Quelle:
List.cs
Quelle:
List.cs

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 werden 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 Basic, IComparer<String^> in Visual C++) implementiert. Der Vergleich funktioniert wie folgt: Zuerst werden die Vergleichszeichen auf nullgetestet, und ein NULL-Verweis wird als kleiner als ein ungleich NULL behandelt. Zweitens werden die Zeichenfolgenlängen verglichen, und die längere Zeichenfolge wird als größer angesehen. Drittens: Wenn die Längen gleich sind, wird ein gewöhnlicher Zeichenfolgenvergleich verwendet.

Eine List<T> von Zeichenfolgen wird erstellt und mit den Namen von fünf pflanzenfressenden Dinosauriern und drei fleischfressenden Dinosauriern bevölkert. Innerhalb jeder der beiden Gruppen haben die Namen keine bestimmte 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 den Bereich der Pflanzenfresser nach "Brachiosaurus" zu durchsuchen. Die Zeichenfolge wird nicht gefunden, und das bitweise Komplement (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 Vergleich passt an, wie die Elemente verglichen werden. Sie können beispielsweise eine CaseInsensitiveComparer instance als Vergleich verwenden, um Zeichenfolgensuchen ohne Berücksichtigung der Groß-/Kleinschreibung durchzuführen.

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

Wenn comparer ist null, überprüft der Standardvergleich Comparer<T>.Default , ob der Typ T die IComparable<T> generische Schnittstelle implementiert, und verwendet diese Implementierung, sofern verfügbar. Wenn dies nicht der Fehler ist, wird überprüft, Comparer<T>.Default ob vom Typ T die IComparable Schnittstelle implementiert wird. Wenn vom Typ T keine schnittstelle implementiert wird, Comparer<T>.Default wird ausgelöst InvalidOperationException.

Muss List<T> bereits nach der Vergleichsimplementierung sortiert werden, andernfalls ist das Ergebnis falsch.

Der Vergleich null mit einem beliebigen Verweistyp ist zulässig und generiert bei Verwendung der IComparable<T> generischen Schnittstelle keine Ausnahme. Beim Sortieren null gilt als kleiner als jedes andere Objekt.

Wenn mehr List<T> als ein Element mit demselben Wert enthält, gibt die Methode nur eines der Vorkommen zurück, und möglicherweise gibt sie eines der Vorkommen zurück, nicht unbedingt das erste.

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

Bei dieser Methode handelt es sich um einen O(log n)-Vorgang, wobei n die Anzahl der Elemente im Bereich ist.

Weitere Informationen

Gilt für: