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