List<T>.BinarySearch Methode
Definition
Wichtig
Einige Informationen beziehen sich auf Vorabversionen, die vor dem Release ggf. grundlegend überarbeitet werden. Microsoft übernimmt hinsichtlich der hier bereitgestellten Informationen keine Gewährleistungen, seien sie ausdrücklich oder konkludent.
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
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
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
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
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.
null
Wenn 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
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
index
und count
geben keinen gültigen Bereich in der List<T> an.
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 null
und 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.
null
Wenn 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.