std::binary_search

Definido en el archivo de encabezado `<algorithm>`
	(1)
`template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );`			(constexpr desde C++20) (hasta C++26)
`template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );`			(desde C++26)
		(2)
`template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );`				(constexpr desde C++20) (hasta C++26)
`template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, class Compare > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );`				(desde C++26)

Comprueba si un elemento equivalente a value aparece dentro del rango particionado [first, last).

1) La equivalencia se comprueba usando operator<:

Si !bool(*iter < value) && !bool(value < *iter) es true para algún iterador iter en [first, last), devuelve true. De lo contrario devuelve false.

Si se cumple alguna de las siguientes condiciones, el comportamiento no está definido:

Para cualquier elemento elem de [first, last), bool(elem < value) no implica !bool(value < elem).
Los elementos elem de [first, last) no están particionados con respecto a las expresiones bool(elem < value) y !bool(value < elem).

(hasta C++20)

Equivalente a std::binary_search(first, last, value, std::less{}).

(desde C++20)

2) La equivalencia se comprueba usando comp:

Si !bool(comp(*iter, value)) && !bool(comp(value, *iter)) es true para algún iterador iter en [first, last), devuelve true. De lo contrario devuelve false.

Si se cumple alguna de las siguientes condiciones, el comportamiento no está definido:

Para cualquier elemento elem de [first, last), bool(comp(elem, value)) no implica !bool(comp(value, elem)).
Los elementos elem de [first, last) no están particionados con respecto a las expresiones bool(comp(elem, value)) y !bool(comp(value, elem)).

Parámetros

first, last	-	El rango de elementos particionados a examinar.
value	-	Valor al cual comparar los elementos.
comp	-	Predicado binario que devuelve `true` Si el primer argumento está ordenado antes del segundo.. La signatura de la función predicado deberá ser equivalente a la siguiente: `bool pred(const Tipo1 &a, const Tipo2 &b);` Mientras que la signatura no necesita tener `const &`, la función no debe modificar los objetos que se le han pasado y debe ser capaz de aceptar todos los valores de tipo (posiblemente `const`) `Tipo1` y `Tipo2` independientemente de la categoría de valor (por lo tanto, no se permite `Tipo1 &`, ni `Tipo1` a menos que para `Tipo1` un movimiento sea equivalente a una copia (desde C++11)). El tipo `Tipo1` debe ser tal que un objeto de tipo `T` puede convertirse implícitamente a `Tipo1`. El tipo `Tipo2` debe ser tal que un objeto de tipo `ForwardIt` puede ser desreferenciado y luego convertido implícitamente a `Tipo2`.
Requisitos de tipo
- `ForwardIt` debe satisfacer los requisitos de ForwardIterator.
- `Compare` debe satisfacer los requisitos de BinaryPredicate. No se requiere que satisfaga a Compare.

Valor de retorno

true si se encuentra un elemento equivalente a value, false de lo contrario.

Complejidad

Dada $\scriptsize N$ $N$ como std::distance(first, last):

1) Como máximo

log 2 (N)+O(1)

comparaciones con value usando operator< (hasta C++20)std::less{} (desde C++20).

2) Como máximo

log 2 (N)+O(1)

aplicaciones del comparador comp.

Sin embargo, si ForwardIt no es un RandomAccessIterator, el número de incrementos del iterador es lineal en $\scriptsize N$ $N$ .

Notas

Aunque std::binary_search solo requiere que [first, last) esté particionado, este algoritmo se usa generalmente en el caso en que [first, last) esté ordenado, de modo que la búsqueda binaria sea válida para cualquier value.

std::binary_search solo verifica si existe un elemento equivalente. Para obtener un iterador para ese elemento (si existe), se debe usar std::lower_bound en su lugar.

Macro de Prueba de característica	Valor	Estándar	Comentario
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Inicialización de lista para algoritmos (1,2)

Posible implementación

Véanse tambián las implementaciones en libstdc++ y libc++.

binary_search (1)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    return std::binary_search(first, last, value, std::less{});
}

binary_search (2)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) and !(comp(value, *first)));
}

Ejemplo

Ejecuta este código

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>

int main()
{
    const auto pajar = {1, 3, 4, 5, 9};
    
    for (const auto aguja : {1, 2, 3})
    {
        std::cout << "Buscando " << aguja << '\n';
        si (std::binary_search(pajar.begin(), pajar.end(), aguja))
            std::cout << "Se encontró " << aguja << '\n';
        else
            std::cout << "¡No se encontró!\n";
    }

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz));
    #else
        assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
    #endif
}

Salida:

Buscando 1
Se encontró 1
Buscando 2
¡No se encontró!
Buscando 3
Se encontró 3

Informes de defectos

Los siguientes informes de defectos de cambio de comportamiento se aplicaron de manera retroactiva a los estándares de C++ publicados anteriormente.

ID	Aplicado a	Comportamiento según lo publicado	Comportamiento correcto
LWG 270	C++98	Se requería que `Compare` satisficiera Compare y se requería que `T` fuera LessThanComparable (se requería un ordenamiento débil estricto).	Solo se requiere una partición; se permiten comparaciones heterogéneas
LWG 787	C++98	Como máximo se admitían $\scriptsize \log_{2}(N)+2$ $log 2 (N)+2$ .	Se corrigió a $\scriptsize \log_{2}(N)+O(1)$ $log 2 (N)+O(1)$ .

Véase también

equal_range	Devuelve el rango de los elementos que coinciden con una clave específica. (plantilla de función) [editar]
lower_bound	Devuelve un iterador al primer elemento no menor que el valor dado. (plantilla de función) [editar]
upper_bound	Devuelve un iterador al primer elemento mayor que un valor determinado. (plantilla de función) [editar]
ranges::binary_search (C++20)	Determina si un elemento existe en un cierto rango. (niebloid) [editar]

Apoyo de compiladores
Implementaciones independientes y albergadas
Lenguaje
Biblioteca estándar
Encabezados de la biblioteca estándar
Requisitos denominados
Macros de prueba de característica (C++20)
Biblioteca de apoyo del lenguaje
Biblioteca de conceptos (C++20)
Biblioteca de diagnósticos
Biblioteca de gestión de memoria
Biblioteca de metaprogramación (C++11)
Biblioteca de servicios generales
Biblioteca de contenedores
Biblioteca de iteradores
Biblioteca de rangos (C++20)
Biblioteca de algoritmos
Biblioteca de cadenas
Biblioteca de procesamiento de texto
Biblioteca numérica
Biblioteca de fecha y hora
Biblioteca de entrada/salida
Biblioteca del sistema de archivos (C++17)
Biblioteca de apoyo de concurrencia (C++11)
Biblioteca de apoyo de ejecución (C++26)
Especificaciones técnicas
Índice de símbolos
Bibliotecas externas

cppreference.com

Buscar

Espacios de nombres

Variantes

Vistas

Acciones