List<T>.BinarySearch Method

Definition

使用对分检索算法在已排序的 List<T> 或它的一部分中查找特定元素。Uses a binary search algorithm to locate a specific element in the sorted List<T> or a portion of it.

Overloads

BinarySearch(T)

使用默认的比较器在整个已排序的 List<T> 中搜索元素,并返回该元素从零开始的索引。Searches the entire sorted List<T> for an element using the default comparer and returns the zero-based index of the element.

BinarySearch(T, IComparer<T>)

使用指定的比较器在整个已排序的 List<T> 中搜索元素,并返回该元素从零开始的索引。Searches the entire sorted List<T> for an element using the specified comparer and returns the zero-based index of the element.

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

使用指定的比较器在已排序 List<T> 的某个元素范围中搜索元素,并返回该元素从零开始的索引。Searches a range of elements in the sorted List<T> for an element using the specified comparer and returns the zero-based index of the element.

BinarySearch(T)

使用默认的比较器在整个已排序的 List<T> 中搜索元素,并返回该元素从零开始的索引。Searches the entire sorted List<T> for an element using the default comparer and returns the zero-based index of the element.

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

Parameters

item
T

要定位的对象。The object to locate. 对于引用类型,该值可以为 nullThe value can be null for reference types.

Returns

Int32

如果找到 item,则为已排序的 List<T>item 的从零开始的索引;否则为一个负数,该负数是大于 item 的下一个元素的索引的按位求补。如果没有更大的元素,则为 Count 的按位求补。The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

Exceptions

此默认比较器 Default 无法找到 IComparable<T> 泛型接口或类型为 TIComparable 接口的实现。The default comparer Default cannot find an implementation of the IComparable<T> generic interface or the IComparable interface for type T.

Examples

下面的示例演示 Sort() 方法重载和 BinarySearch(T) 方法重载。The following example demonstrates the Sort() method overload and the BinarySearch(T) method overload. 创建一个字符串 List<T>,并以无特定顺序填充四个字符串。A List<T> of strings is created and populated with four strings, in no particular order. 将显示并排序列表,并再次显示该列表。The list is displayed, sorted, and displayed again.

然后,使用 BinarySearch(T) 方法重载搜索列表中没有的两个字符串,Insert 方法用于插入它们。The BinarySearch(T) method overload is then used to search for two strings that are not in the list, and the Insert method is used to insert them. 在每种情况下,BinarySearch(T) 方法的返回值为负,因为字符串不在列表中。The return value of the BinarySearch(T) method is negative in each case, because the strings are not in the list. 采用按位求补(和视觉对象C# C++中的 ~ 运算符,在 Visual Basic 中为 Xor-1)会生成列表中大于搜索字符串的第一个元素的索引,并且在此位置插入将保留排序顺序。Taking the bitwise complement (the ~ operator in C# and Visual C++, Xor -1 in Visual Basic) of this negative number produces the index of the first element in the list that is larger than the search string, and inserting at this location preserves the sort order. 第二个搜索字符串大于列表中的任何元素,因此插入位置在列表的末尾。The second search string is larger than any element in the list, so the insertion position is at the end of the list.

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

Remarks

此方法使用 T 类型的默认比较器 Comparer<T>.Default 来确定列表元素的顺序。This method uses the default comparer Comparer<T>.Default for type T to determine the order of list elements. Comparer<T>.Default 属性检查类型 T 是否实现 IComparable<T> 泛型接口,并使用该实现(如果可用)。The Comparer<T>.Default property checks whether type T implements the IComparable<T> generic interface and uses that implementation, if available. 否则,Comparer<T>.Default 会检查类型 T 是否实现了 IComparable 接口。If not, Comparer<T>.Default checks whether type T implements the IComparable interface. 如果类型 T 未实现任何一个接口,Comparer<T>.Default 将引发一个 InvalidOperationExceptionIf type T does not implement either interface, Comparer<T>.Default throws an InvalidOperationException.

List<T> 必须已根据比较器实现进行排序;否则,结果不正确。The List<T> must already be sorted according to the comparer implementation; otherwise, the result is incorrect.

使用 IComparable<T> 泛型接口时,允许比较 null 与任何引用类型,并且不会生成异常。Comparing null with any reference type is allowed and does not generate an exception when using the IComparable<T> generic interface. 进行排序时,null 被视为小于任何其他对象。When sorting, null is considered to be less than any other object.

如果 List<T> 包含多个具有相同值的元素,则此方法只返回其中一个匹配项,并且它可能会返回任何一个匹配项,而不一定是第一个匹配项。If the List<T> contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.

如果 List<T> 不包含指定的值,则该方法将返回一个负整数。If the List<T> does not contain the specified value, the method returns a negative integer. 可以将按位求补运算(~)应用于此负整数,以获取大于搜索值的第一个元素的索引。You can apply the bitwise complement operation (~) to this negative integer to get the index of the first element that is larger than the search value. List<T>中插入值时,应将此索引用作插入点来维护排序顺序。When inserting the value into the List<T>, this index should be used as the insertion point to maintain the sort order.

此方法是 O (log n)操作,其中n是范围中元素的数目。This method is an O(log n) operation, where n is the number of elements in the range.

See also

BinarySearch(T, IComparer<T>)

使用指定的比较器在整个已排序的 List<T> 中搜索元素,并返回该元素从零开始的索引。Searches the entire sorted List<T> for an element using the specified comparer and returns the zero-based index of the element.

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

Parameters

item
T

要定位的对象。The object to locate. 对于引用类型,该值可以为 nullThe value can be null for reference types.

comparer
IComparer<T>

比较元素时要使用的 IComparer<T> 实现。The IComparer<T> implementation to use when comparing elements.

- 或 --or- 如果使用默认比较器 Default,则为 nullnull to use the default comparer Default.

Returns

Int32

如果找到 item,则为已排序的 List<T>item 的从零开始的索引;否则为一个负数,该负数是大于 item 的下一个元素的索引的按位求补。如果没有更大的元素,则为 Count 的按位求补。The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

Exceptions

comparernull,并且默认比较器 Default 找不到 IComparable<T> 泛型接口或类型为 TIComparable 接口的实现。comparer is null, and the default comparer Default cannot find an implementation of the IComparable<T> generic interface or the IComparable interface for type T.

Examples

下面的示例演示 Sort(IComparer<T>) 方法重载和 BinarySearch(T, IComparer<T>) 方法重载。The following example demonstrates the Sort(IComparer<T>) method overload and the BinarySearch(T, IComparer<T>) method overload.

该示例定义了一个名为 DinoCompare 的字符串的替代比较器,该比较器实现 IComparer<string>IComparer(Of String) 在C++Visual Basic 中 IComparer<String^> 在视觉对象中)泛型接口。The example defines an alternative comparer for strings named DinoCompare, which implements the IComparer<string> (IComparer(Of String) in Visual Basic, IComparer<String^> in Visual C++) generic interface. 比较器的工作方式如下所示:首先,为 null测试比较规则,并将 null 引用视为小于非空引用。The comparer works as follows: First, the comparands are tested for null, and a null reference is treated as less than a non-null. 其次,比较字符串长度,较长的字符串被认为更大。Second, the string lengths are compared, and the longer string is deemed to be greater. 第三,如果长度相等,则使用普通字符串比较。Third, if the lengths are equal, ordinary string comparison is used.

创建一个字符串 List<T>,并以无特定顺序填充四个字符串。A List<T> of strings is created and populated with four strings, in no particular order. 随即显示列表,使用替代比较器对其进行排序,并再次显示。The list is displayed, sorted using the alternate comparer, and displayed again.

然后,使用 BinarySearch(T, IComparer<T>) 方法重载搜索未在列表中的多个字符串,同时采用备用比较器。The BinarySearch(T, IComparer<T>) method overload is then used to search for several strings that are not in the list, employing the alternate comparer. Insert 方法用于插入字符串。The Insert method is used to insert the strings. 这两个方法位于名为 SearchAndInsert的函数中,同时还包含采用按位求补的代码(Visual Basic C# Xor 和C++中的 ~ 运算符),并使用该负数作为 BinarySearch(T, IComparer<T>) 返回的负数,并将其用作插入新字符串的索引。These two methods are located in the function named SearchAndInsert, along with code to take the bitwise complement (the ~ operator in C# and Visual C++, Xor -1 in Visual Basic) of the negative number returned by BinarySearch(T, IComparer<T>) and use it as an index for inserting the new string.

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

Remarks

比较器自定义元素的比较方式。The comparer customizes how the elements are compared. 例如,可以将 CaseInsensitiveComparer 实例用作比较器来执行不区分大小写的字符串搜索。For example, you can use a CaseInsensitiveComparer instance as the comparer to perform case-insensitive string searches.

如果提供了 comparer,则使用指定的 IComparer<T> 实现将 List<T> 的元素与指定的值进行比较。If comparer is provided, the elements of the List<T> are compared to the specified value using the specified IComparer<T> implementation.

如果 null``comparer,则默认比较器 Comparer<T>.Default 检查类型 T 是否实现 IComparable<T> 泛型接口,并使用该实现(如果可用)。If comparer is null, the default comparer Comparer<T>.Default checks whether type T implements the IComparable<T> generic interface and uses that implementation, if available. 否则,Comparer<T>.Default 会检查类型 T 是否实现了 IComparable 接口。If not, Comparer<T>.Default checks whether type T implements the IComparable interface. 如果类型 T 未实现任何一个接口,Comparer<T>.Default 将引发 InvalidOperationExceptionIf type T does not implement either interface, Comparer<T>.Default throws InvalidOperationException.

List<T> 必须已根据比较器实现进行排序;否则,结果不正确。The List<T> must already be sorted according to the comparer implementation; otherwise, the result is incorrect.

使用 IComparable<T> 泛型接口时,允许比较 null 与任何引用类型,并且不会生成异常。Comparing null with any reference type is allowed and does not generate an exception when using the IComparable<T> generic interface. 进行排序时,null 被视为小于任何其他对象。When sorting, null is considered to be less than any other object.

如果 List<T> 包含多个具有相同值的元素,则此方法只返回其中一个匹配项,并且它可能会返回任何一个匹配项,而不一定是第一个匹配项。If the List<T> contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.

如果 List<T> 不包含指定的值,则该方法将返回一个负整数。If the List<T> does not contain the specified value, the method returns a negative integer. 可以将按位求补运算(~)应用于此负整数,以获取大于搜索值的第一个元素的索引。You can apply the bitwise complement operation (~) to this negative integer to get the index of the first element that is larger than the search value. List<T>中插入值时,应将此索引用作插入点来维护排序顺序。When inserting the value into the List<T>, this index should be used as the insertion point to maintain the sort order.

此方法是 O (log n)操作,其中n是范围中元素的数目。This method is an O(log n) operation, where n is the number of elements in the range.

See also

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

使用指定的比较器在已排序 List<T> 的某个元素范围中搜索元素,并返回该元素从零开始的索引。Searches a range of elements in the sorted List<T> for an element using the specified comparer and returns the zero-based index of the element.

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

Parameters

index
Int32

要搜索范围的从零开始的起始索引。The zero-based starting index of the range to search.

count
Int32

要搜索的范围的长度。The length of the range to search.

item
T

要定位的对象。The object to locate. 对于引用类型,该值可以为 nullThe value can be null for reference types.

comparer
IComparer<T>

比较元素时要使用的 IComparer<T> 实现,若要使用默认比较器 Default,则为 nullThe IComparer<T> implementation to use when comparing elements, or null to use the default comparer Default.

Returns

Int32

如果找到 item,则为已排序的 List<T>item 的从零开始的索引;否则为一个负数,该负数是大于 item 的下一个元素的索引的按位求补。如果没有更大的元素,则为 Count 的按位求补。The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

Exceptions

index 小于 0。index is less than 0.

- 或 --or- count 小于 0。count is less than 0.

indexcount 不表示 List<T> 中的有效范围。index and count do not denote a valid range in the List<T>.

comparernull,并且默认比较器 Default 找不到 IComparable<T> 泛型接口或类型为 TIComparable 接口的实现。comparer is null, and the default comparer Default cannot find an implementation of the IComparable<T> generic interface or the IComparable interface for type T.

Examples

下面的示例演示 Sort(Int32, Int32, IComparer<T>) 方法重载和 BinarySearch(Int32, Int32, T, IComparer<T>) 方法重载。The following example demonstrates the Sort(Int32, Int32, IComparer<T>) method overload and the BinarySearch(Int32, Int32, T, IComparer<T>) method overload.

该示例定义了一个名为 DinoCompare 的字符串的替代比较器,该比较器实现 IComparer<string>IComparer(Of String) 在C++Visual Basic 中 IComparer<String^> 在视觉对象中)泛型接口。The example defines an alternative comparer for strings named DinoCompare, which implements the IComparer<string> (IComparer(Of String) in Visual Basic, IComparer<String^> in Visual C++) generic interface. 比较器的工作方式如下所示:首先,为 null测试比较规则,并将 null 引用视为小于非空引用。The comparer works as follows: First, the comparands are tested for null, and a null reference is treated as less than a non-null. 其次,比较字符串长度,较长的字符串被认为更大。Second, the string lengths are compared, and the longer string is deemed to be greater. 第三,如果长度相等,则使用普通字符串比较。Third, if the lengths are equal, ordinary string comparison is used.

创建一个字符串 List<T>,并使用5个 herbivorous 恐龙和3个 carnivorous 恐龙的名称填充。A List<T> of strings is created and populated with the names of five herbivorous dinosaurs and three carnivorous dinosaurs. 这两个组中的每个组的名称不是任何特定的排序顺序。Within each of the two groups, the names are not in any particular sort order. 随即显示列表,使用替代比较器对 herbivores 的范围进行排序,并再次显示该列表。The list is displayed, the range of herbivores is sorted using the alternate comparer, and the list is displayed again.

然后,使用 BinarySearch(Int32, Int32, T, IComparer<T>) 方法重载来仅搜索 "Brachiosaurus" 的 herbivores 范围。The BinarySearch(Int32, Int32, T, IComparer<T>) method overload is then used to search only the range of herbivores for "Brachiosaurus". 找不到该字符串,并且由 BinarySearch(Int32, Int32, T, IComparer<T>) 方法返回的负数的按C#位求C++补(和中的 ~ 运算符 Xor-Visual Basic 1)用作插入新字符串的索引。The string is not found, and the bitwise complement (the ~ operator in C# and Visual C++, Xor -1 in Visual Basic) of the negative number returned by the BinarySearch(Int32, Int32, T, IComparer<T>) method is used as an index for inserting the new string.

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

Remarks

比较器自定义元素的比较方式。The comparer customizes how the elements are compared. 例如,可以将 CaseInsensitiveComparer 实例用作比较器来执行不区分大小写的字符串搜索。For example, you can use a CaseInsensitiveComparer instance as the comparer to perform case-insensitive string searches.

如果提供了 comparer,则使用指定的 IComparer<T> 实现将 List<T> 的元素与指定的值进行比较。If comparer is provided, the elements of the List<T> are compared to the specified value using the specified IComparer<T> implementation.

如果 null``comparer,则默认比较器 Comparer<T>.Default 检查类型 T 是否实现 IComparable<T> 泛型接口,并使用该实现(如果可用)。If comparer is null, the default comparer Comparer<T>.Default checks whether type T implements the IComparable<T> generic interface and uses that implementation, if available. 否则,Comparer<T>.Default 会检查类型 T 是否实现了 IComparable 接口。If not, Comparer<T>.Default checks whether type T implements the IComparable interface. 如果类型 T 未实现任何一个接口,Comparer<T>.Default 将引发 InvalidOperationExceptionIf type T does not implement either interface, Comparer<T>.Default throws InvalidOperationException.

List<T> 必须已根据比较器实现进行排序;否则,结果不正确。The List<T> must already be sorted according to the comparer implementation; otherwise, the result is incorrect.

使用 IComparable<T> 泛型接口时,允许比较 null 与任何引用类型,并且不会生成异常。Comparing null with any reference type is allowed and does not generate an exception when using the IComparable<T> generic interface. 进行排序时,null 被视为小于任何其他对象。When sorting, null is considered to be less than any other object.

如果 List<T> 包含多个具有相同值的元素,则此方法只返回其中一个匹配项,并且它可能会返回任何一个匹配项,而不一定是第一个匹配项。If the List<T> contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.

如果 List<T> 不包含指定的值,则该方法将返回一个负整数。If the List<T> does not contain the specified value, the method returns a negative integer. 可以将按位求补运算(~)应用于此负整数,以获取大于搜索值的第一个元素的索引。You can apply the bitwise complement operation (~) to this negative integer to get the index of the first element that is larger than the search value. List<T>中插入值时,应将此索引用作插入点来维护排序顺序。When inserting the value into the List<T>, this index should be used as the insertion point to maintain the sort order.

此方法是 O (log n)操作,其中n是范围中元素的数目。This method is an O(log n) operation, where n is the number of elements in the range.

See also

Applies to