Bagikan melalui

List<T>.BinarySearch Metode

  • Referensi

Definisi

Ruang nama:
System.Collections.Generic
Rakitan:
System.Collections.dll
Rakitan:
mscorlib.dll
Rakitan:
netstandard.dll

Menggunakan algoritma pencarian biner untuk menemukan elemen tertentu dalam bagian yang diurutkan List<T> atau sebagiannya.

Overload

BinarySearch(T)

Mencari seluruh yang diurutkan List<T> untuk elemen menggunakan perbandingan default dan mengembalikan indeks elemen berbasis nol.
BinarySearch(T, IComparer<T>)

Mencari seluruh yang diurutkan List<T> untuk elemen menggunakan perbandingan yang ditentukan dan mengembalikan indeks elemen berbasis nol.
BinarySearch(Int32, Int32, T, IComparer<T>)

Mencari rentang elemen dalam yang diurutkan List<T> untuk elemen menggunakan perbandingan yang ditentukan dan mengembalikan indeks elemen berbasis nol.

BinarySearch(T)

Sumber:
List.cs
Sumber:
List.cs
Sumber:
List.cs

Mencari seluruh yang diurutkan List<T> untuk elemen menggunakan perbandingan default dan mengembalikan indeks elemen berbasis nol.

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

Objek yang akan ditemukan. Nilainya bisa null untuk jenis referensi.

Mengembalikan

Int32

Indeks item berbasis nol dalam yang diurutkan List<T>, jika item ditemukan; jika tidak, angka negatif yang merupakan pelengkap bitwise dari indeks elemen berikutnya yang lebih besar dari atau, jika tidak ada elemen yang lebih item besar, pelengkap bitwise .Count

Pengecualian

InvalidOperationException

Pembanding Default default tidak dapat menemukan implementasi IComparable<T> antarmuka generik atau IComparable antarmuka untuk jenis T.

Contoh

Contoh berikut menunjukkan Sort() metode kelebihan beban dan BinarySearch(T) metode kelebihan beban. List<T> String dibuat dan diisi dengan empat string, tanpa urutan tertentu. Daftar ditampilkan, diurutkan, dan ditampilkan lagi.

Metode BinarySearch(T) kelebihan beban kemudian digunakan untuk mencari dua string yang tidak ada dalam daftar, dan Insert metode ini digunakan untuk menyisipkannya. Nilai BinarySearch(T) pengembalian metode negatif dalam setiap kasus, karena string tidak ada dalam daftar. Mengambil pelengkap bitwise (operator ~ di C# dan Visual C++, Xor -1 di Visual Basic) dari angka negatif ini menghasilkan indeks elemen pertama dalam daftar yang lebih besar dari string pencarian, dan menyisipkan di lokasi ini mempertahankan urutan pengurutan. String pencarian kedua lebih besar dari elemen apa pun dalam daftar, sehingga posisi penyisipan berada di akhir daftar.

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

Keterangan

Metode ini menggunakan perbandingan Comparer<T>.Default default untuk jenis T untuk menentukan urutan elemen daftar. Properti Comparer<T>.Default memeriksa apakah jenis T mengimplementasikan antarmuka generik dan menggunakan implementasi tersebut IComparable<T> , jika tersedia. Jika tidak, Comparer<T>.Default memeriksa apakah jenis T mengimplementasikan IComparable antarmuka. Jika jenis T tidak mengimplementasikan salah satu antarmuka, Comparer<T>.Default melempar .InvalidOperationException

List<T> harus sudah diurutkan sesuai dengan implementasi perbandingan; jika tidak, hasilnya salah.

Membandingkan null dengan jenis referensi apa pun diizinkan dan tidak menghasilkan pengecualian saat menggunakan IComparable<T> antarmuka generik. Saat mengurutkan, null dianggap kurang dari objek lainnya.

List<T> Jika berisi lebih dari satu elemen dengan nilai yang sama, metode hanya mengembalikan salah satu kemunculan, dan mungkin mengembalikan salah satu kemunculan, belum tentu yang pertama.

List<T> Jika tidak berisi nilai yang ditentukan, metode mengembalikan bilangan bulat negatif. Anda dapat menerapkan operasi pelengkap bitwise (~) ke bilangan bulat negatif ini untuk mendapatkan indeks elemen pertama yang lebih besar dari nilai pencarian. Saat menyisipkan nilai ke dalam List<T>, indeks ini harus digunakan sebagai titik penyisipan untuk mempertahankan urutan pengurutan.

Metode ini adalah operasi O(log n), di mana n adalah jumlah elemen dalam rentang.

Lihat juga

Berlaku untuk

BinarySearch(T, IComparer<T>)

Sumber:
List.cs
Sumber:
List.cs
Sumber:
List.cs

Mencari seluruh yang diurutkan List<T> untuk elemen menggunakan perbandingan yang ditentukan dan mengembalikan indeks elemen berbasis nol.

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

Objek yang akan ditemukan. Nilainya bisa null untuk jenis referensi.

comparer
IComparer<T>

Implementasi yang IComparer<T> digunakan saat membandingkan elemen.

-atau-

null untuk menggunakan perbandingan Defaultdefault .

Mengembalikan

Int32

Indeks item berbasis nol dalam yang diurutkan List<T>, jika item ditemukan; jika tidak, angka negatif yang merupakan pelengkap bitwise dari indeks elemen berikutnya yang lebih besar dari atau, jika tidak ada elemen yang lebih item besar, pelengkap bitwise .Count

Pengecualian

InvalidOperationException

comparer adalah null, dan perbandingan Default default tidak dapat menemukan implementasi IComparable<T> antarmuka generik atau IComparable antarmuka untuk jenis T.

Contoh

Contoh berikut menunjukkan Sort(IComparer<T>) metode kelebihan beban dan BinarySearch(T, IComparer<T>) metode kelebihan beban.

Contoh mendefinisikan perbandingan alternatif untuk string bernama DinoCompare, yang mengimplementasikan IComparer<string> antarmuka generik (IComparer(Of String) di Visual Basic, IComparer<String^> di Visual C++). Perbandingan berfungsi sebagai berikut: Pertama, perbandingan diuji untuk null, dan referensi null diperlakukan kurang dari non-null. Kedua, panjang string dibandingkan, dan string yang lebih panjang dianggap lebih besar. Ketiga, jika panjangnya sama, perbandingan string biasa digunakan.

List<T> String dibuat dan diisi dengan empat string, tanpa urutan tertentu. Daftar ditampilkan, diurutkan menggunakan perbandingan alternatif, dan ditampilkan lagi.

Metode BinarySearch(T, IComparer<T>) kelebihan beban kemudian digunakan untuk mencari beberapa string yang tidak ada dalam daftar, menggunakan perbandingan alternatif. Metode Insert ini digunakan untuk menyisipkan string. Kedua metode ini terletak dalam fungsi bernama SearchAndInsert, bersama dengan kode untuk mengambil pelengkap bitwise (operator ~ di C# dan Visual C++, Xor -1 di Visual Basic) dari angka negatif yang dikembalikan oleh BinarySearch(T, IComparer<T>) dan menggunakannya sebagai indeks untuk menyisipkan string baru.

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

Keterangan

Perbandingan menyesuaikan bagaimana elemen dibandingkan. Misalnya, Anda dapat menggunakan CaseInsensitiveComparer instans sebagai pembanding untuk melakukan pencarian string yang tidak peka huruf besar/kecil.

Jika comparer disediakan, elemen List<T> dibandingkan dengan nilai yang ditentukan menggunakan implementasi yang ditentukan IComparer<T> .

Jika comparer adalah null, pembanding Comparer<T>.Default default memeriksa apakah jenis T mengimplementasikan antarmuka generik dan menggunakan implementasi tersebut IComparable<T> , jika tersedia. Jika tidak, Comparer<T>.Default memeriksa apakah jenis T mengimplementasikan IComparable antarmuka. Jika jenis T tidak mengimplementasikan salah satu antarmuka, Comparer<T>.Default lemparkan InvalidOperationException.

List<T> harus sudah diurutkan sesuai dengan implementasi perbandingan; jika tidak, hasilnya salah.

Membandingkan null dengan jenis referensi apa pun diizinkan dan tidak menghasilkan pengecualian saat menggunakan IComparable<T> antarmuka generik. Saat mengurutkan, null dianggap kurang dari objek lainnya.

List<T> Jika berisi lebih dari satu elemen dengan nilai yang sama, metode hanya mengembalikan salah satu kemunculan, dan mungkin mengembalikan salah satu kemunculan, belum tentu yang pertama.

List<T> Jika tidak berisi nilai yang ditentukan, metode mengembalikan bilangan bulat negatif. Anda dapat menerapkan operasi pelengkap bitwise (~) ke bilangan bulat negatif ini untuk mendapatkan indeks elemen pertama yang lebih besar dari nilai pencarian. Saat menyisipkan nilai ke dalam List<T>, indeks ini harus digunakan sebagai titik penyisipan untuk mempertahankan urutan pengurutan.

Metode ini adalah operasi O(log n), di mana n adalah jumlah elemen dalam rentang.

Lihat juga

Berlaku untuk

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

Sumber:
List.cs
Sumber:
List.cs
Sumber:
List.cs

Mencari rentang elemen dalam yang diurutkan List<T> untuk elemen menggunakan perbandingan yang ditentukan dan mengembalikan indeks elemen berbasis nol.

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

Indeks awal berbasis nol dari rentang yang akan dicari.

count
Int32

Panjang rentang untuk dicari.

item
T

Objek yang akan ditemukan. Nilainya bisa null untuk jenis referensi.

comparer
IComparer<T>

Implementasi IComparer<T> yang digunakan saat membandingkan elemen, atau null untuk menggunakan perbandingan Defaultdefault .

Mengembalikan

Int32

Indeks item berbasis nol dalam yang diurutkan List<T>, jika item ditemukan; jika tidak, angka negatif yang merupakan pelengkap bitwise dari indeks elemen berikutnya yang lebih besar dari atau, jika tidak ada elemen yang lebih item besar, pelengkap bitwise .Count

Pengecualian

ArgumentOutOfRangeException

index kurang dari 0.

-atau-

count kurang dari 0.

ArgumentException

index dan count jangan menandakan rentang yang valid dalam List<T>.

InvalidOperationException

comparer adalah null, dan perbandingan Default default tidak dapat menemukan implementasi IComparable<T> antarmuka generik atau IComparable antarmuka untuk jenis T.

Contoh

Contoh berikut menunjukkan Sort(Int32, Int32, IComparer<T>) metode kelebihan beban dan BinarySearch(Int32, Int32, T, IComparer<T>) metode kelebihan beban.

Contoh mendefinisikan perbandingan alternatif untuk string bernama DinoCompare, yang mengimplementasikan IComparer<string> antarmuka generik (IComparer(Of String) di Visual Basic, IComparer<String^> di Visual C++). Perbandingan berfungsi sebagai berikut: Pertama, perbandingan diuji untuk null, dan referensi null diperlakukan kurang dari non-null. Kedua, panjang string dibandingkan, dan string yang lebih panjang dianggap lebih besar. Ketiga, jika panjangnya sama, perbandingan string biasa digunakan.

Sebuah List<T> string dibuat dan diisi dengan nama lima dinosawati herbivora dan tiga dinosang karnivora. Dalam masing-masing dari dua grup, nama tidak dalam urutan pengurutan tertentu. Daftar ditampilkan, rentang herbivora diurutkan menggunakan perbandingan alternatif, dan daftar ditampilkan lagi.

Metode BinarySearch(Int32, Int32, T, IComparer<T>) kelebihan beban kemudian digunakan untuk mencari hanya rentang herbivora untuk "Brachiosaurus". String tidak ditemukan, dan pelengkap bitwise (operator ~ di C# dan Visual C++, Xor -1 di Visual Basic) dari angka negatif yang dikembalikan oleh BinarySearch(Int32, Int32, T, IComparer<T>) metode digunakan sebagai indeks untuk menyisipkan string baru.

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

Keterangan

Perbandingan menyesuaikan bagaimana elemen dibandingkan. Misalnya, Anda dapat menggunakan CaseInsensitiveComparer instans sebagai pembanding untuk melakukan pencarian string yang tidak peka huruf besar/kecil.

Jika comparer disediakan, elemen List<T> dibandingkan dengan nilai yang ditentukan menggunakan implementasi yang ditentukan IComparer<T> .

Jika comparer adalah null, pembanding Comparer<T>.Default default memeriksa apakah jenis T mengimplementasikan antarmuka generik dan menggunakan implementasi tersebut IComparable<T> , jika tersedia. Jika tidak, Comparer<T>.Default memeriksa apakah jenis T mengimplementasikan IComparable antarmuka. Jika jenis T tidak mengimplementasikan salah satu antarmuka, Comparer<T>.Default lemparkan InvalidOperationException.

List<T> harus sudah diurutkan sesuai dengan implementasi perbandingan; jika tidak, hasilnya salah.

Membandingkan null dengan jenis referensi apa pun diizinkan dan tidak menghasilkan pengecualian saat menggunakan IComparable<T> antarmuka generik. Saat mengurutkan, null dianggap kurang dari objek lainnya.

List<T> Jika berisi lebih dari satu elemen dengan nilai yang sama, metode hanya mengembalikan salah satu kemunculan, dan mungkin mengembalikan salah satu kemunculan, belum tentu yang pertama.

List<T> Jika tidak berisi nilai yang ditentukan, metode mengembalikan bilangan bulat negatif. Anda dapat menerapkan operasi pelengkap bitwise (~) ke bilangan bulat negatif ini untuk mendapatkan indeks elemen pertama yang lebih besar dari nilai pencarian. Saat menyisipkan nilai ke dalam List<T>, indeks ini harus digunakan sebagai titik penyisipan untuk mempertahankan urutan pengurutan.

Metode ini adalah operasi O(log n), di mana n adalah jumlah elemen dalam rentang.

Lihat juga

Berlaku untuk