Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::binary_search: testar pertença num intervalo ordenado

std::binary_search devolve um booleano que indica se um intervalo ordenado contém um elemento equivalente à chave.

Versão: C++23

Sintaxe

template<class ForwardIt, class T>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value);

template<class ForwardIt, class T, class Compare>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);

std::binary_search, de <algorithm>, examina [first, last) e devolve true quando existe um elemento equivalente a value segundo o comparador. Não devolve posição nem número de duplicados; usa lower_bound ou equal_range para isso.

A pré-condição é o particionamento para esta chave concreta nos dois sentidos e a assimetria: se comp(e, value) for verdadeiro, comp(value, e) tem de ser falso. Ordenar tudo pela mesma ordem coerente é condição suficiente segura, mas não necessária para uma chave. Violar o particionamento ou a assimetria causa comportamento indefinido. Um intervalo vazio devolve false.

O número de comparações é logarítmico. Com iteradores de acesso aleatório, os passos também; outras categorias podem exigir incrementos lineares. O comparador tem de definir uma ordem coerente e não modificar elementos.

Exemplos

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array values{1, 3, 5, 7};
    std::cout << std::binary_search(values.begin(), values.end(), 5) << '\n';
}

Resultado

1

std::binary_search → 1

Fontes