List<T>.BinarySearch Método

Definição

Namespace:

System.Collections.Generic

Assembly:

System.Collections.dll

Usa um algoritmo de pesquisa binária para localizar um elemento específico no List<T> classificado ou parte dele.

Sobrecargas

BinarySearch(T)	Pesquisa todo o List<T> classificado para um elemento usando o comparador padrão e retorna o índice baseado em zero do elemento.
BinarySearch(T, IComparer<T>)	Pesquisa um elemento em todo o List<T> classificado usando o comparador especificado e retorna o índice baseado em zero do elemento.
BinarySearch(Int32, Int32, T, IComparer<T>)	Pesquisa um intervalo de elementos no List<T> classificado para encontrar um elemento que usa o comparador especificado e retorna o índice baseado em zero do elemento.

BinarySearch(T)

Origem:

List.cs

Pesquisa todo o List<T> classificado para um elemento usando o comparador padrão e retorna o índice baseado em zero do elemento.

C#

public int BinarySearch (T item);

Parâmetros

item

T

O objeto a ser localizado. O valor pode ser null para tipos de referência.

Retornos

Int32

O índice baseado em zero da item no List<T> classificado, se item for encontrado; caso contrário, um número negativo que é o complemento bit a bit do índice do próximo elemento maior que item, ou, se não houver nenhum elemento maior, o complemento bit a bit de Count.

Exceções

InvalidOperationException

O comparador padrão Default não consegue encontrar uma implementação da interface genérica IComparable<T> ou a interface IComparable para o tipo T.

Exemplos

O exemplo a seguir demonstra a sobrecarga do Sort() método e a sobrecarga do BinarySearch(T) método. Um List<T> de cadeias de caracteres é criado e preenchido com quatro cadeias de caracteres, em nenhuma ordem específica. A lista é exibida, classificada e exibida novamente.

Em BinarySearch(T) seguida, a sobrecarga do método é usada para pesquisar duas cadeias de caracteres que não estão na lista e o Insert método é usado para inseri-las. O valor retornado do BinarySearch(T) método é negativo em cada caso, pois as cadeias de caracteres não estão na lista. Usar o complemento bit a bit (o operador ~ em C# e Visual C++, Xor -1 no Visual Basic) desse número negativo produz o índice do primeiro elemento na lista que é maior que a cadeia de caracteres de pesquisa e a inserção nesse local preserva a ordem de classificação. A segunda cadeia de caracteres de pesquisa é maior que qualquer elemento na lista, portanto, a posição de inserção está no final da lista.

C#

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
*/

Comentários

Esse método usa o comparador Comparer<T>.Default padrão para o tipo T para determinar a ordem dos elementos de lista. A Comparer<T>.Default propriedade verifica se o tipo T implementa a IComparable<T> interface genérica e usa essa implementação, se disponível. Caso contrário, Comparer<T>.Default verifica se o tipo T implementa a IComparable interface. Se o tipo T não implementar nenhuma das interfaces, Comparer<T>.Default gerará um InvalidOperationException.

O List<T> já deve ser classificado de acordo com a implementação do comparador; caso contrário, o resultado está incorreto.

A comparação null com qualquer tipo de referência é permitida e não gera uma exceção ao usar a IComparable<T> interface genérica. Durante a classificação, null é considerado menor que qualquer outro objeto.

Se o List<T> contiver mais de um elemento com o mesmo valor, o método retornará apenas uma das ocorrências e poderá retornar qualquer uma das ocorrências, não necessariamente a primeira.

Caso o List<T> não contenha o valor especificado, o método retorna um inteiro negativo. Você pode aplicar a operação de complemento bit a bit (~) a esse inteiro negativo para obter o índice do primeiro elemento maior que o valor de pesquisa. Ao inserir o valor no List<T>, esse índice deve ser usado como o ponto de inserção para manter a ordem de classificação.

Esse método é uma operação O(log n), em que n é o número de elementos no intervalo.

Confira também

• Executando operações de cadeia de caracteres Culture-Insensitive em coleções

BinarySearch(T, IComparer<T>)

Origem:

List.cs

Pesquisa um elemento em todo o List<T> classificado usando o comparador especificado e retorna o índice baseado em zero do elemento.

C#

public int BinarySearch (T item, System.Collections.Generic.IComparer<T>? comparer);

Parâmetros

item

T

O objeto a ser localizado. O valor pode ser null para tipos de referência.

comparer

IComparer<T>

A implementação de IComparer<T> a ser usada durante a comparação de elementos.

- ou -

null para usar o comparador padrão Default.

Retornos

Int32

O índice baseado em zero da item no List<T> classificado, se item for encontrado; caso contrário, um número negativo que é o complemento bit a bit do índice do próximo elemento maior que item, ou, se não houver nenhum elemento maior, o complemento bit a bit de Count.

Exceções

InvalidOperationException

comparer é null e o comparador padrão Default não consegue encontrar uma implementação da interface genérica IComparable<T> ou a interface IComparable para o tipo T.

Exemplos

O exemplo a seguir demonstra a sobrecarga do Sort(IComparer<T>) método e a sobrecarga do BinarySearch(T, IComparer<T>) método.

O exemplo define um comparador alternativo para cadeias de caracteres chamada DinoCompare, que implementa a IComparer<string> interface genérica (IComparer(Of String) no Visual Basic, IComparer<String^> no Visual C++). O comparador funciona da seguinte maneira: primeiro, os comparands são testados para nulle uma referência nula é tratada como menor que um não nulo. Em segundo lugar, os comprimentos da cadeia de caracteres são comparados e a cadeia de caracteres mais longa é considerada maior. Em terceiro lugar, se os comprimentos forem iguais, a comparação de cadeia de caracteres comum será usada.

Um List<T> de cadeias de caracteres é criado e preenchido com quatro cadeias de caracteres, em nenhuma ordem específica. A lista é exibida, classificada usando o comparador alternativo e exibida novamente.

Em BinarySearch(T, IComparer<T>) seguida, a sobrecarga do método é usada para pesquisar várias cadeias de caracteres que não estão na lista, empregando o comparador alternativo. O Insert método é usado para inserir as cadeias de caracteres. Esses dois métodos estão localizados na função chamada SearchAndInsert, juntamente com o código para usar o complemento bit a bit (o operador ~ em C# e Visual C++, Xor -1 no Visual Basic) do número negativo retornado por BinarySearch(T, IComparer<T>) e usá-lo como um índice para inserir a nova cadeia de caracteres.

C#

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
 */

Comentários

A comparação personaliza como os elementos são comparados. Por exemplo, você pode usar uma CaseInsensitiveComparer instância como o comparador para executar pesquisas de cadeia de caracteres que não diferenciam maiúsculas de minúsculas.

Se comparer for fornecido, os elementos do List<T> serão comparados com o valor especificado usando a implementação especificada IComparer<T> .

Se comparer for null, o comparador Comparer<T>.Default padrão verificará se o tipo T implementa a IComparable<T> interface genérica e usa essa implementação, se disponível. Caso contrário, Comparer<T>.Default verifica se o tipo T implementa a IComparable interface. Se o tipo T não implementar nenhuma das interfaces, Comparer<T>.Default gerará InvalidOperationException.

O List<T> já deve ser classificado de acordo com a implementação do comparador; caso contrário, o resultado está incorreto.

A comparação null com qualquer tipo de referência é permitida e não gera uma exceção ao usar a IComparable<T> interface genérica. Durante a classificação, null é considerado menor que qualquer outro objeto.

Se o List<T> contiver mais de um elemento com o mesmo valor, o método retornará apenas uma das ocorrências e poderá retornar qualquer uma das ocorrências, não necessariamente a primeira.

Caso o List<T> não contenha o valor especificado, o método retorna um inteiro negativo. Você pode aplicar a operação de complemento bit a bit (~) a esse inteiro negativo para obter o índice do primeiro elemento maior que o valor de pesquisa. Ao inserir o valor no List<T>, esse índice deve ser usado como o ponto de inserção para manter a ordem de classificação.

Esse método é uma operação O(log n), em que n é o número de elementos no intervalo.

Confira também

• Executando operações de cadeia de caracteres Culture-Insensitive em coleções

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

Origem:

List.cs

Pesquisa um intervalo de elementos no List<T> classificado para encontrar um elemento que usa o comparador especificado e retorna o índice baseado em zero do elemento.

C#

public int BinarySearch (int index, int count, T item, System.Collections.Generic.IComparer<T>? comparer);

Parâmetros

index

Int32

O índice baseado em zero inicial do intervalo a ser pesquisado.

count

Int32

O tamanho do intervalo a ser procurado.

item

T

O objeto a ser localizado. O valor pode ser null para tipos de referência.

comparer

IComparer<T>

A implementação IComparer<T> a ser usada na comparação de elementos ou null para usar o comparador padrão Default.

Retornos

Int32

O índice baseado em zero da item no List<T> classificado, se item for encontrado; caso contrário, um número negativo que é o complemento bit a bit do índice do próximo elemento maior que item, ou, se não houver nenhum elemento maior, o complemento bit a bit de Count.

Exceções

ArgumentOutOfRangeException

index é menor que 0.

- ou -

count é menor que 0.

ArgumentException

index e count não denotam um intervalo válido em List<T>.

InvalidOperationException

comparer é null e o comparador padrão Default não consegue encontrar uma implementação da interface genérica IComparable<T> ou a interface IComparable para o tipo T.

Exemplos

O exemplo a seguir demonstra a sobrecarga do Sort(Int32, Int32, IComparer<T>) método e a sobrecarga do BinarySearch(Int32, Int32, T, IComparer<T>) método.

O exemplo define um comparador alternativo para cadeias de caracteres chamada DinoCompare, que implementa a IComparer<string> interface genérica (IComparer(Of String) no Visual Basic, IComparer<String^> no Visual C++). O comparador funciona da seguinte maneira: primeiro, os comparands são testados para nulle uma referência nula é tratada como menor que um não nulo. Em segundo lugar, os comprimentos da cadeia de caracteres são comparados e a cadeia de caracteres mais longa é considerada maior. Em terceiro lugar, se os comprimentos forem iguais, a comparação de cadeia de caracteres comum será usada.

Uma List<T> das cadeias de caracteres é criada e preenchida com os nomes de cinco dinossauros herbívoros e três dinossauros carnívoros. Em cada um dos dois grupos, os nomes não estão em nenhuma ordem de classificação específica. A lista é exibida, o intervalo de herbívoros é classificado usando o comparador alternativo e a lista é exibida novamente.

Em BinarySearch(Int32, Int32, T, IComparer<T>) seguida, a sobrecarga do método é usada para pesquisar apenas o intervalo de herbívoros para "Brachisauro". A cadeia de caracteres não foi encontrada e o complemento bit a bit (o operador ~ em C# e Visual C++, Xor -1 no Visual Basic) do número negativo retornado pelo BinarySearch(Int32, Int32, T, IComparer<T>) método é usado como um índice para inserir a nova cadeia de caracteres.

C#

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
 */

Comentários

A comparação personaliza como os elementos são comparados. Por exemplo, você pode usar uma CaseInsensitiveComparer instância como o comparador para executar pesquisas de cadeia de caracteres que não diferenciam maiúsculas de minúsculas.

Se comparer for fornecido, os elementos do List<T> serão comparados com o valor especificado usando a implementação especificada IComparer<T> .

Se comparer for null, o comparador Comparer<T>.Default padrão verificará se o tipo T implementa a IComparable<T> interface genérica e usa essa implementação, se disponível. Caso contrário, Comparer<T>.Default verifica se o tipo T implementa a IComparable interface. Se o tipo T não implementar nenhuma das interfaces, Comparer<T>.Default gerará InvalidOperationException.

O List<T> já deve ser classificado de acordo com a implementação do comparador; caso contrário, o resultado está incorreto.

A comparação null com qualquer tipo de referência é permitida e não gera uma exceção ao usar a IComparable<T> interface genérica. Durante a classificação, null é considerado menor que qualquer outro objeto.

Se o List<T> contiver mais de um elemento com o mesmo valor, o método retornará apenas uma das ocorrências e poderá retornar qualquer uma das ocorrências, não necessariamente a primeira.

Caso o List<T> não contenha o valor especificado, o método retorna um inteiro negativo. Você pode aplicar a operação de complemento bit a bit (~) a esse inteiro negativo para obter o índice do primeiro elemento maior que o valor de pesquisa. Ao inserir o valor no List<T>, esse índice deve ser usado como o ponto de inserção para manter a ordem de classificação.

Esse método é uma operação O(log n), em que n é o número de elementos no intervalo.

Confira também

• IComparer<T>
• IComparable<T>
• Executando operações de cadeia de caracteres Culture-Insensitive em coleções