List<T>.BinarySearch Metoda

  • Reference

Definice

Obor názvů:
System.Collections.Generic
Sestavení:
System.Collections.dll
Sestavení:
mscorlib.dll
Sestavení:
netstandard.dll

Používá binární vyhledávací algoritmus k vyhledání konkrétního prvku v seřazené List<T> nebo jeho části.

Přetížení

BinarySearch(T)

Vyhledá celý seřazený List<T> prvek pomocí výchozího porovnávače a vrátí index elementu založeného na nule.
BinarySearch(T, IComparer<T>)

Vyhledá celý seřazený List<T> prvek pomocí zadaného porovnávače a vrátí index elementu založeného na nule.
BinarySearch(Int32, Int32, T, IComparer<T>)

Vyhledá oblast prvků v seřazené List<T> pro prvek pomocí zadaného porovnávače a vrátí nulový index elementu.

BinarySearch(T)

Source:
List.cs
Source:
List.cs
Source:
List.cs

Vyhledá celý seřazený List<T> prvek pomocí výchozího porovnávače a vrátí index elementu založeného na nule.

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

Parametry

item
T

Objekt, který chcete najít. Hodnota může být null pro referenční typy.

Návraty

Int32

Nulový index v seřazené List<T>hodnotě , pokud item je nalezen; v opačném případě záporné číslo, které je bitovým doplňkem indexu dalšího prvku, který je větší než item nebo, pokud není větší prvek, bitový doplněk Count.item

Výjimky

InvalidOperationException

Výchozí porovnávače Default nemůže najít implementaci IComparable<T> obecného rozhraní nebo IComparable rozhraní pro typ T.

Příklady

Následující příklad ukazuje Sort() přetížení metody a BinarySearch(T) přetížení metody. Řetězec řetězce List<T> se vytvoří a naplní čtyřmi řetězci v žádném konkrétním pořadí. Seznam se zobrazí, seřadí a znovu zobrazí.

Přetížení BinarySearch(T) metody se pak použije k vyhledání dvou řetězců, které nejsou v seznamu, a Insert metoda se použije k jejich vložení. Návratová hodnota BinarySearch(T) metody je v každém případě záporná, protože řetězce nejsou v seznamu. Když vezmete bitový doplněk (operátor ~ v jazyce C# a Visual C++, Xor -1 v jazyce Visual Basic) tohoto záporného čísla vytvoří index prvního prvku v seznamu, který je větší než hledaný řetězec, a vložením do tohoto umístění zachováte pořadí řazení. Druhý hledaný řetězec je větší než kterýkoli prvek v seznamu, takže pozice vložení je na konci seznamu.

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

Poznámky

Tato metoda používá výchozí porovnávací nástroj Comparer<T>.Default pro typ T k určení pořadí prvků seznamu. Vlastnost Comparer<T>.Default kontroluje, zda typ T implementuje IComparable<T> obecné rozhraní a používá tuto implementaci, pokud je k dispozici. Pokud ne, zkontroluje, Comparer<T>.Default jestli typ T implementuje IComparable rozhraní. Pokud type T neimplementuje rozhraní, Comparer<T>.Default vyvolá příkaz InvalidOperationException.

Musí List<T> být již seřazena podle implementace porovnávače, jinak je výsledek nesprávný.

Porovnání null s libovolným referenčním typem je povoleno a při použití IComparable<T> obecného rozhraní nevygeneruje výjimku. Při řazení null se považuje za menší než jakýkoli jiný objekt.

List<T> Pokud obsahuje více než jeden prvek se stejnou hodnotou, vrátí metoda pouze jeden z výskytů a může vrátit kterýkoli z výskytů, ne nutně první.

List<T> Pokud hodnota neobsahuje zadanou hodnotu, vrátí metoda záporné celé číslo. Můžete použít bitové doplňovací operace (~) na toto záporné celé číslo a získat index prvního prvku, který je větší než hledaná hodnota. Při vkládání hodnoty do objektu List<T>by se tento index měl použít jako kurzor, aby se zachovalo pořadí řazení.

Tato metoda je operace O(log n), kde n je počet prvků v oblasti.

Viz také

Platí pro

BinarySearch(T, IComparer<T>)

Source:
List.cs
Source:
List.cs
Source:
List.cs

Vyhledá celý seřazený List<T> prvek pomocí zadaného porovnávače a vrátí index elementu založeného na nule.

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

Parametry

item
T

Objekt, který chcete najít. Hodnota může být null pro referenční typy.

comparer
IComparer<T>

Implementace IComparer<T> , která se má použít při porovnávání prvků.

-nebo-

null k použití výchozího porovnávače Default.

Návraty

Int32

Nulový index v seřazené List<T>hodnotě , pokud item je nalezen; v opačném případě záporné číslo, které je bitovým doplňkem indexu dalšího prvku, který je větší než item nebo, pokud není větší prvek, bitový doplněk Count.item

Výjimky

InvalidOperationException

comparer je nulla výchozí porovnávače Default nemůže najít implementaci IComparable<T> obecného rozhraní nebo IComparable rozhraní pro typ T.

Příklady

Následující příklad ukazuje Sort(IComparer<T>) přetížení metody a BinarySearch(T, IComparer<T>) přetížení metody.

Příklad definuje alternativní porovnávací nástroj pro řetězce s názvem DinoCompare, který implementuje IComparer<string> obecné rozhraní (IComparer(Of String) v jazyce Visual Basic, IComparer<String^> v jazyce Visual C++). Porovnávací nástroj funguje takto: Nejprve se testují nullporovnání pro a nulový odkaz je považován za menší než nulový. Za druhé se porovnávají délky řetězců a delší řetězec se považuje za větší. Za třetí, pokud jsou délky stejné, použije se porovnání běžných řetězců.

Řetězec řetězce List<T> se vytvoří a naplní čtyřmi řetězci v žádném konkrétním pořadí. Seznam se zobrazí, seřadí pomocí alternativního porovnávače a znovu se zobrazí.

Přetížení BinarySearch(T, IComparer<T>) metody se pak použije k vyhledání několika řetězců, které nejsou v seznamu, a využívá alternativní porovnávač. Metoda Insert se používá k vložení řetězců. Tyto dvě metody se nacházejí ve funkci s názvem SearchAndInsert, spolu s kódem, který převezme bitový doplněk (operátor ~ v jazyce C# a Visual C++, Xor -1 v jazyce Visual Basic) záporného čísla vráceného uživatelem BinarySearch(T, IComparer<T>) a použije ho jako index pro vložení nového řetězce.

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

Poznámky

Porovnávací metoda přizpůsobuje způsob porovnání prvků. Instanci můžete například použít CaseInsensitiveComparer jako porovnávací nástroj k vyhledávání řetězců bez rozlišování velkých a malých písmen.

Pokud comparer je zadán, elementy List<T> jsou porovnány se zadanou hodnotou pomocí zadané IComparer<T> implementace.

Pokud comparer je null, výchozí porovnávací nástroj Comparer<T>.Default zkontroluje, jestli typ T implementuje IComparable<T> obecné rozhraní a používá tuto implementaci, pokud je k dispozici. Pokud ne, zkontroluje, Comparer<T>.Default jestli typ T implementuje IComparable rozhraní. Pokud typ T neimplementuje ani rozhraní, Comparer<T>.Default vyvolá InvalidOperationException.

Musí List<T> být již seřazena podle implementace porovnávače, jinak je výsledek nesprávný.

Porovnání null s libovolným referenčním typem je povoleno a při použití IComparable<T> obecného rozhraní nevygeneruje výjimku. Při řazení null se považuje za menší než jakýkoli jiný objekt.

List<T> Pokud obsahuje více než jeden prvek se stejnou hodnotou, vrátí metoda pouze jeden z výskytů a může vrátit kterýkoli z výskytů, ne nutně první.

List<T> Pokud hodnota neobsahuje zadanou hodnotu, vrátí metoda záporné celé číslo. Můžete použít bitové doplňovací operace (~) na toto záporné celé číslo a získat index prvního prvku, který je větší než hledaná hodnota. Při vkládání hodnoty do objektu List<T>by se tento index měl použít jako kurzor, aby se zachovalo pořadí řazení.

Tato metoda je operace O(log n), kde n je počet prvků v oblasti.

Viz také

Platí pro

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

Source:
List.cs
Source:
List.cs
Source:
List.cs

Vyhledá oblast prvků v seřazené List<T> pro prvek pomocí zadaného porovnávače a vrátí nulový index elementu.

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

Parametry

index
Int32

Počáteční index od nuly oblasti, která se má hledat.

count
Int32

Délka prohledávaného rozsahu.

item
T

Objekt, který chcete najít. Hodnota může být null pro referenční typy.

comparer
IComparer<T>

Implementace IComparer<T> , která se má použít při porovnávání prvků, nebo null pro použití výchozího porovnávače Default.

Návraty

Int32

Nulový index v seřazené List<T>hodnotě , pokud item je nalezen; v opačném případě záporné číslo, které je bitovým doplňkem indexu dalšího prvku, který je větší než item nebo, pokud není větší prvek, bitový doplněk Count.item

Výjimky

ArgumentOutOfRangeException

index je menší než 0.

-nebo-

count je menší než 0.

ArgumentException

index a count neoznamujte platný rozsah v List<T>.

InvalidOperationException

comparer je nulla výchozí porovnávače Default nemůže najít implementaci IComparable<T> obecného rozhraní nebo IComparable rozhraní pro typ T.

Příklady

Následující příklad ukazuje Sort(Int32, Int32, IComparer<T>) přetížení metody a BinarySearch(Int32, Int32, T, IComparer<T>) přetížení metody.

Příklad definuje alternativní porovnávací nástroj pro řetězce s názvem DinoCompare, který implementuje IComparer<string> obecné rozhraní (IComparer(Of String) v jazyce Visual Basic, IComparer<String^> v jazyce Visual C++). Porovnávací nástroj funguje takto: Nejprve se testují nullporovnání pro a nulový odkaz je považován za menší než nulový. Za druhé se porovnávají délky řetězců a delší řetězec se považuje za větší. Za třetí, pokud jsou délky stejné, použije se porovnání běžných řetězců.

Řetězec List<T> je vytvořen a naplněn jmény pěti býložravých dinosaurů a tří masožravých dinosaurů. V každé z těchto dvou skupin nejsou názvy v žádném konkrétním pořadí řazení. Zobrazí se seznam, rozsah býložravých se seřadí pomocí alternativního porovnávače a seznam se znovu zobrazí.

Přetížení BinarySearch(Int32, Int32, T, IComparer<T>) metody se pak používá k vyhledávání pouze rozsahu býložravci pro "Brachiosaurus". Řetězec nebyl nalezen a bitový doplněk (operátor ~ v jazyce C# a Visual C++, Xor -1 v jazyce Visual Basic) záporného čísla vráceného metodou BinarySearch(Int32, Int32, T, IComparer<T>) se použije jako index pro vložení nového řetězce.

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

Poznámky

Porovnávací metoda přizpůsobuje způsob porovnání prvků. Instanci můžete například použít CaseInsensitiveComparer jako porovnávací nástroj k vyhledávání řetězců bez rozlišování velkých a malých písmen.

Pokud comparer je zadán, elementy List<T> jsou porovnány se zadanou hodnotou pomocí zadané IComparer<T> implementace.

Pokud comparer je null, výchozí porovnávací nástroj Comparer<T>.Default zkontroluje, jestli typ T implementuje IComparable<T> obecné rozhraní a používá tuto implementaci, pokud je k dispozici. Pokud ne, zkontroluje, Comparer<T>.Default jestli typ T implementuje IComparable rozhraní. Pokud typ T neimplementuje ani rozhraní, Comparer<T>.Default vyvolá InvalidOperationException.

Musí List<T> být již seřazena podle implementace porovnávače, jinak je výsledek nesprávný.

Porovnání null s libovolným referenčním typem je povoleno a při použití IComparable<T> obecného rozhraní nevygeneruje výjimku. Při řazení null se považuje za menší než jakýkoli jiný objekt.

List<T> Pokud obsahuje více než jeden prvek se stejnou hodnotou, vrátí metoda pouze jeden z výskytů a může vrátit kterýkoli z výskytů, ne nutně první.

List<T> Pokud hodnota neobsahuje zadanou hodnotu, vrátí metoda záporné celé číslo. Můžete použít bitové doplňovací operace (~) na toto záporné celé číslo a získat index prvního prvku, který je větší než hledaná hodnota. Při vkládání hodnoty do objektu List<T>by se tento index měl použít jako kurzor, aby se zachovalo pořadí řazení.

Tato metoda je operace O(log n), kde n je počet prvků v oblasti.

Viz také

Platí pro