List<T>.BinarySearch メソッド

定義

バイナリ サーチ アルゴリズムを使用して、並べ替えられた List<T> 内の特定の要素またはその一部を検索します。

オーバーロード

BinarySearch(T)

既定の比較子を使用して、並べ替えられた要素の List<T> 全体を検索し、その要素の 0 から始まるインデックスを返します。

BinarySearch(T, IComparer<T>)

指定した比較子を使用して、並べ替えられた要素の List<T> 全体を検索し、その要素の 0 から始まるインデックスを返します。

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

指定した比較子を使用して、並べ替えられた要素の List<T> の 1 つの要素の範囲を検索し、その要素の 0 から始まるインデックスを返します。

BinarySearch(T)

既定の比較子を使用して、並べ替えられた要素の List<T> 全体を検索し、その要素の 0 から始まるインデックスを返します。

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

パラメーター

item
T

検索するオブジェクト。 参照型の場合は null の値を使用できます。

戻り値

Int32

item が見つかった場合は、並べ替えられた List<T> 内の item の 0 から始まるインデックス。見つからなかった場合は、負の値。これは、item の次に大きい要素のインデックスのビットごとの補数です。ただし、大きい要素が存在しない場合は、Count のビットごとの補数です。

例外

既定の比較関数 Default は、IComparable<T> ジェネリック インターフェイスまたは T 型の IComparable インターフェイスの実装を見つけることができません。

次の例では、メソッドの Sort() オーバーロードとメソッドのオーバーロードを BinarySearch(T) 示します。 List<T> 1 つの文字列が作成され、4 つの文字列が順不同で入力されます。 一覧が表示され、並べ替えられて、もう一度表示されます。

BinarySearch(T)その後、リストにない 2 つの文字列を検索するためにメソッド オーバーロードが使用されInsert、メソッドを使用して挿入されます。 文字列がリストに含まれていないため、メソッドの BinarySearch(T) 戻り値はいずれの場合も負の値になります。 この負の数のビットごとの補数 (C# と Visual C++ の ~ 演算子、Visual Basicでは -1) を取得すると、 Xor リスト内の最初の要素のインデックスが検索文字列よりも大きくなり、この場所に挿入すると並べ替え順序が保持されます。 2 番目の検索文字列はリスト内のどの要素よりも大きいため、挿入位置はリストの末尾にあります。

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

注釈

このメソッドは、型Tの既定の比較子Comparer<T>.Defaultを使用して、リスト要素の順序を決定します。 このプロパティは Comparer<T>.Default 、型 T がジェネリック インターフェイスを IComparable<T> 実装し、使用可能な場合はその実装を使用するかどうかを確認します。 そうでない場合は、 Comparer<T>.DefaultT がインターフェイスを IComparable 実装しているかどうかを確認します。 型 T がどちらのインターフェイスも実装していない場合は、 Comparer<T>.Default InvalidOperationException.

比較子の List<T> 実装に従って既に並べ替える必要があります。それ以外の場合は、結果が正しくありません。

任意の null 参照型との比較は許可され、ジェネリック インターフェイスを使用する場合は例外は IComparable<T> 生成されません。 並べ替え時に、 null 他のどのオブジェクトよりも小さいと見なされます。

同じ値を List<T> 持つ複数の要素が含まれている場合、メソッドは 1 つの出現回数のみを返し、必ずしも最初の要素ではなく、いずれかの出現を返す可能性があります。

List<T>指定した値が含まれていない場合、メソッドは負の整数を返します。 この負の整数にビットごとの補数演算 (~) を適用して、検索値より大きい最初の要素のインデックスを取得できます。 値を挿入するときは、並べ替え順序を List<T>維持するために、このインデックスを挿入ポイントとして使用する必要があります。

このメソッドは O (ログ n) 演算です。 ここで、n は範囲内の要素の数です。

こちらもご覧ください

適用対象

BinarySearch(T, IComparer<T>)

指定した比較子を使用して、並べ替えられた要素の List<T> 全体を検索し、その要素の 0 から始まるインデックスを返します。

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

パラメーター

item
T

検索するオブジェクト。 参照型の場合は null の値を使用できます。

comparer
IComparer<T>

要素を比較する場合に使用する IComparer<T> の実装。

  • または - 既定の比較子 Default を使用する場合は null

戻り値

Int32

item が見つかった場合は、並べ替えられた List<T> 内の item の 0 から始まるインデックス。見つからなかった場合は、負の値。これは、item の次に大きい要素のインデックスのビットごとの補数です。ただし、大きい要素が存在しない場合は、Count のビットごとの補数です。

例外

comparernull で、既定の比較関数 DefaultIComparable<T> ジェネリック インターフェイスまたは T 型の IComparable インターフェイスの実装を見つけることができません。

次の例では、メソッドの Sort(IComparer<T>) オーバーロードとメソッドのオーバーロードを BinarySearch(T, IComparer<T>) 示します。

この例では、DinoCompare という名前の文字列の代替比較子を定義します。これは、(IComparer(Of String)Visual Basicでは Visual IComparer<String^> C++ では) ジェネリック インターフェイスを実装IComparer<string>します。 比較子は次のように動作します。まず、比較対象がテストされ null、null 参照が null 以外の参照未満として扱われます。 次に、文字列の長さが比較され、長い文字列が大きいと見なされます。 3 つ目は、長さが等しい場合は、通常の文字列比較が使用されます。

List<T> 1 つの文字列が作成され、4 つの文字列が順不同で入力されます。 リストが表示され、代替比較子を使用して並べ替えられて、もう一度表示されます。

その後、メソッドの BinarySearch(T, IComparer<T>) オーバーロードを使用して、リストに含まれていない複数の文字列を検索し、代替比較子を使用します。 この Insert メソッドは、文字列の挿入に使用されます。 これら 2 つのメソッドは、返される負の数BinarySearch(T, IComparer<T>)のビットごとの補数 (C# と Visual C++ の ~ 演算子、Visual Basicでは -1) を受け取り、 Xor 新しい文字列を挿入するためのインデックスとして使用するコードと共に、名前付きのSearchAndInsert関数に配置されます。

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

注釈

比較子は、要素の比較方法をカスタマイズします。 たとえば、インスタンスを CaseInsensitiveComparer 比較子として使用して、大文字と小文字を区別しない文字列検索を実行できます。

指定した場合 comparer 、指定された実装を List<T> 使用して、指定した値の要素が比較されます IComparer<T>

ある場合comparer、既定の比較子Comparer<T>.Defaultnull、型Tがジェネリック インターフェイスをIComparable<T>実装しているかどうかを確認し、使用可能な場合は、その実装を使用します。 そうでない場合は、 Comparer<T>.DefaultT がインターフェイスを IComparable 実装しているかどうかを確認します。 型Tがどちらのインターフェイスも実装していない場合は、Comparer<T>.Default.InvalidOperationException

比較子の List<T> 実装に従って既に並べ替える必要があります。それ以外の場合は、結果が正しくありません。

任意の null 参照型との比較は許可され、ジェネリック インターフェイスを使用する場合は例外は IComparable<T> 生成されません。 並べ替え時に、 null 他のどのオブジェクトよりも小さいと見なされます。

同じ値を List<T> 持つ複数の要素が含まれている場合、メソッドは 1 つの出現回数のみを返し、必ずしも最初の要素ではなく、いずれかの出現を返す可能性があります。

List<T>指定した値が含まれていない場合、メソッドは負の整数を返します。 この負の整数にビットごとの補数演算 (~) を適用して、検索値より大きい最初の要素のインデックスを取得できます。 値を挿入するときは、並べ替え順序を List<T>維持するために、このインデックスを挿入ポイントとして使用する必要があります。

このメソッドは O (ログ n) 演算です。 ここで、n は範囲内の要素の数です。

こちらもご覧ください

適用対象

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

指定した比較子を使用して、並べ替えられた要素の List<T> の 1 つの要素の範囲を検索し、その要素の 0 から始まるインデックスを返します。

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

パラメーター

index
Int32

検索範囲の開始位置を示す 0 から始まるインデックス。

count
Int32

検索する範囲の長さ。

item
T

検索するオブジェクト。 参照型の場合は null の値を使用できます。

comparer
IComparer<T>

要素を比較する場合に使用する IComparer<T> 実装。または、既定の比較子 Default を使用する場合は null

戻り値

Int32

item が見つかった場合は、並べ替えられた List<T> 内の item の 0 から始まるインデックス。見つからなかった場合は、負の値。これは、item の次に大きい要素のインデックスのビットごとの補数です。ただし、大きい要素が存在しない場合は、Count のビットごとの補数です。

例外

index が 0 未満です。

または count が 0 未満です。

index および countList<T> において有効な範囲を表していません。

comparernull で、既定の比較関数 DefaultIComparable<T> ジェネリック インターフェイスまたは T 型の IComparable インターフェイスの実装を見つけることができません。

次の例では、メソッドオーバーロード Sort(Int32, Int32, IComparer<T>) とメソッドオーバーロードを BinarySearch(Int32, Int32, T, IComparer<T>) 示します。

この例では、DinoCompare という名前の文字列の代替比較子を定義します。DinoCompare は、(IComparer(Of String)visual C++ では Visual BasicIComparer<String^>) ジェネリック インターフェイスを実装IComparer<string>します。 比較子は次のように機能します。まず、比較対象がテストされ null、null 参照は null 以外の参照より小さいものとして扱われます。 次に、文字列の長さが比較され、長い文字列が大きいと見なされます。 3 番目に、長さが等しい場合は、通常の文字列比較が使用されます。

List<T> 5つの草食恐竜と3つの肉食恐竜の名前が作成され、設定されています。 2 つの各グループ内では、名前は特定の並べ替え順序ではありません。 一覧が表示され、草食の範囲が代替比較子を使用して並べ替えられて、一覧が再び表示されます。

BinarySearch(Int32, Int32, T, IComparer<T>)その後、このメソッド オーバーロードを使用して、草食の範囲のみを検索して "Brachiosaurus" を検索します。 文字列が見つからず、メソッドによってBinarySearch(Int32, Int32, T, IComparer<T>)返される負の数のビットごとの補数 (C# と Visual C++ の ~ 演算子、 Xor Visual Basicでは -1) が、新しい文字列を挿入するためのインデックスとして使用されます。

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

注釈

比較子は、要素の比較方法をカスタマイズします。 たとえば、インスタンスを CaseInsensitiveComparer 比較子として使用して、大文字と小文字を区別しない文字列検索を実行できます。

指定した場合 comparer 、指定された実装を List<T> 使用して、指定した値の要素が比較されます IComparer<T>

ある場合comparer、既定の比較子Comparer<T>.Defaultnull、型Tがジェネリック インターフェイスをIComparable<T>実装しているかどうかを確認し、使用可能な場合は、その実装を使用します。 そうでない場合は、 Comparer<T>.DefaultT がインターフェイスを IComparable 実装しているかどうかを確認します。 型Tがどちらのインターフェイスも実装していない場合は、Comparer<T>.Default.InvalidOperationException

比較子の List<T> 実装に従って既に並べ替える必要があります。それ以外の場合は、結果が正しくありません。

任意の null 参照型との比較は許可され、ジェネリック インターフェイスを使用する場合は例外は IComparable<T> 生成されません。 並べ替え時に、 null 他のオブジェクトよりも小さいと見なされます。

同じ値を List<T> 持つ複数の要素が含まれている場合、メソッドは 1 つの出現回数のみを返し、必ずしも最初の要素ではなく、いずれかの出現箇所を返す可能性があります。

List<T>指定した値が含まれていない場合、メソッドは負の整数を返します。 この負の整数にビットごとの補数演算 (~) を適用して、検索値より大きい最初の要素のインデックスを取得できます。 値を挿入するときは、並べ替え順序を List<T>維持するために、このインデックスを挿入ポイントとして使用する必要があります。

このメソッドは O(log n) 演算で、 n は範囲内の要素の数です。

こちらもご覧ください

適用対象