Pesquisa Binária C++ STL

Use std::binary_search quando precisar saber se um valor está presente em um intervalo ordenado. A função retorna um resultado booleano de pertinência; não retorna o iterador correspondente nem a quantidade de valores encontrados. Ela pode ser usada com um vetor, um array ou outro intervalo com iteradores adequados, desde que os requisitos de ordenação sejam atendidos.

Entenda os requisitos de std::binary_search

O intervalo pesquisado precisa estar particionado de acordo com a comparação usada na busca. No uso mais comum, isso significa que os elementos devem estar em ordem crescente, seguindo a mesma ordenação da comparação padrão. Se o intervalo não estiver ordenado dessa forma, o resultado não será uma resposta confiável sobre a presença do valor. Ordenar os elementos e depois alterá-los, mesmo que parcialmente, também pode invalidar essa condição prévia.

O par de iteradores descreve um intervalo semiaberto, [first, last): first aponta para o primeiro elemento considerado, enquanto last aponta para a posição logo após o último elemento e fica fora do intervalo. Passar container.begin() e container.end() pesquisa todo o contêiner. Um intervalo vazio é válido e indica que não houve correspondência; em um intervalo de um elemento, esse elemento é incluído quando first aponta para ele e last vem logo depois.

O resultado é true quando há um elemento equivalente segundo a ordenação e false caso contrário. Se precisar da posição, use uma operação como std::lower_bound e verifique se o iterador retornado não é last e se o valor é equivalente. std::binary_search por si só não identifica qual ocorrência duplicada foi encontrada.

Use std::binary_search com um intervalo ordenado

Inclua <algorithm> para usar a função, <iostream> para exibir resultados e <vector> para este contêiner. O programa completo a seguir verifica um valor presente e outro ausente. O texto usa diretamente o resultado booleano, tornando os dois casos visíveis sem depender de um iterador. Os rótulos e a saída exibidos no exemplo permanecem em inglês.

Execute este exemplo:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

O vetor já está ordenado, e cada chamada recebe o intervalo completo de iteradores. Altere qualquer um dos valores procurados para adaptar o exemplo; mantenha o vetor na mesma ordem esperada pela busca. A função não ordena o intervalo por conta própria.

Pesquise com um comparador personalizado

Para um tipo definido pelo usuário, passe um comparador que determine a ordenação do intervalo. Antes da busca, ordene os elementos usando esse mesmo comparador. Neste exemplo, os registros são ordenados pela idade, e considera-se que o valor está presente quando há um registro com essa idade. O nome não faz parte do critério de equivalência deste comparador.

O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

#include <algorithm>
#include <string>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

O comparador compara valores, não iteradores. Ele precisa definir a ordenação usada para organizar o intervalo e ser compatível com as comparações entre os elementos do intervalo e o valor procurado. Aqui, dois registros com a mesma idade são equivalentes para esta busca, mesmo que tenham nomes diferentes. Se a aplicação precisar distingui-los, inclua os campos que fazem essa distinção na ordenação ou use outra estratégia de busca.

Evite erros comuns em buscas binárias

• Pesquisar dados desordenados: ordene o intervalo primeiro. Ordenar por uma chave e pesquisar com outra ordenação não atende ao requisito da busca.
• Tratar last como um elemento: last fica fora do intervalo. Use container.end() para pesquisar o contêiner inteiro; não o desreferencie.
• Esperar um iterador: o tipo de retorno é booleano. Use std::lower_bound quando precisar de uma posição e verifique o resultado antes de desreferenciá-lo.
• Usar um comparador incompatível: a ordenação usada na classificação e na busca precisa ser compatível, inclusive quanto à equivalência. Se o comparador considerar dois registros equivalentes, a resposta sobre a presença seguirá esse critério, e não todos os campos do registro.

Essas verificações tornam o resultado da função significativo. A biblioteca executa a busca, mas não consegue detectar se o intervalo foi preparado com outra ordenação ou se o comparador não corresponde aos dados.