Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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

Fuentes