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 od nuly.
BinarySearch(T, IComparer<T>)

Vyhledá celý seřazený List<T> prvek pomocí zadaného porovnávače a vrátí index prvku od nuly.
BinarySearch(Int32, Int32, T, IComparer<T>)

Vyhledá v rozsahu prvků v seřazené List<T> prvek pomocí zadaného porovnávače a vrátí index prvku od nuly.

BinarySearch(T)

Zdroj:
List.cs
Zdroj:
List.cs
Zdroj:
List.cs

Vyhledá celý seřazený List<T> prvek pomocí výchozího porovnávače a vrátí index elementu od nuly.

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 odkazové typy.

Návraty

Int32

V seřazené hodnotě se nachází index item od nuly. V opačném případě se jedná o záporné číslo, které je bitovým doplňkem indexu dalšího prvku, který je větší než item nebo, pokud neexistuje větší prvek, bitový doplněk Count.List<T>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 List<T> řetězce 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í. Vrácená hodnota BinarySearch(T) metody je v každém případě záporná, protože řetězce nejsou v seznamu. Když vezmeme 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í do tohoto umístění zachová pořadí řazení. Druhý hledaný řetězec je větší než jaký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 typ T neimplementuje ani jeden z rozhraní, Comparer<T>.Default vyvolá .InvalidOperationException

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

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

List<T> Pokud objekt 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 neobsahuje zadanou hodnotu, vrátí metoda záporné celé číslo. U tohoto záporného celého čísla můžete použít bitový doplněk (~) a získat tak index prvního prvku, který je větší než hledaná hodnota. Při vkládání hodnoty do List<T>by se tento index měl použít jako kurzor pro zachování pořadí řazení.

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

Viz také

Platí pro

BinarySearch(T, IComparer<T>)

Zdroj:
List.cs
Zdroj:
List.cs
Zdroj:
List.cs

Vyhledá celý seřazený List<T> prvek pomocí zadaného porovnávače a vrátí index prvku od nuly.

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 odkazové 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

V seřazené hodnotě se nachází index item od nuly. V opačném případě se jedná o záporné číslo, které je bitovým doplňkem indexu dalšího prvku, který je větší než item nebo, pokud neexistuje větší prvek, bitový doplněk Count.List<T>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í a pro a nulový odkaz se považuje 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ého řetězce.

Řetězec List<T> řetězce 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žívá k vyhledání několika řetězců, které nejsou v seznamu, a využívá alternativní porovnávací nástroj. Metoda Insert se používá k vložení řetězců. Tyto dvě metody jsou umístěny ve funkci s názvem SearchAndInsertspolu 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 metodou 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 provádění řetězcového vyhledávání nerozlišující malá a velká písmena.

Pokud comparer je zadán, prvky jsou List<T> 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.

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

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

List<T> Pokud objekt 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 neobsahuje zadanou hodnotu, vrátí metoda záporné celé číslo. U tohoto záporného celého čísla můžete použít bitový doplněk (~) a získat tak index prvního prvku, který je větší než hledaná hodnota. Při vkládání hodnoty do List<T>by se tento index měl použít jako kurzor pro zachování pořadí řazení.

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

Viz také

Platí pro

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

Zdroj:
List.cs
Zdroj:
List.cs
Zdroj:
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 oblasti, která se má prohledávat od nuly.

count
Int32

Délka prohledávaného rozsahu.

item
T

Objekt, který chcete najít. Hodnota může být null pro odkazové 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

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í a pro a nulový odkaz se považuje 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ého řetězce.

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

Přetížení BinarySearch(Int32, Int32, T, IComparer<T>) metody se pak používá k vyhledá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é 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 provádění řetězcového vyhledávání nerozlišující malá a velká písmena.

Pokud comparer je zadán, prvky jsou List<T> 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.

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

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

List<T> Pokud objekt 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 neobsahuje zadanou hodnotu, vrátí metoda záporné celé číslo. U tohoto záporného celého čísla můžete použít bitový doplněk (~) a získat tak index prvního prvku, který je větší než hledaná hodnota. Při vkládání hodnoty do List<T>by se tento index měl použít jako kurzor pro zachování pořadí řazení.

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

Viz také

Platí pro