CKTIS / C++
std::binary_search: comprobar pertenencia en un rango ordenado
std::binary_search devuelve un booleano que indica si un rango ordenado contiene un elemento equivalente a la clave.
Versión: C++23
Sintaxis
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) y devuelve true si existe un elemento equivalente a value según el comparador. No devuelve posición ni cantidad de duplicados; para ello usa lower_bound o equal_range.
La precondición es que el rango esté particionado para esta clave concreta en ambos sentidos y que haya asimetría: si comp(e, value) es verdadero, comp(value, e) debe ser falso. Ordenar todo con el mismo orden coherente es una condición suficiente segura, pero no necesaria para una sola clave. Violar la partición o asimetría causa comportamiento indefinido. Un rango vacío devuelve false.
El número de comparaciones es logarítmico. Con iteradores de acceso aleatorio también lo es el recorrido; otras categorías pueden necesitar incrementos lineales. El comparador debe definir un orden coherente y no modificar elementos.
Ejemplos
#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