Namespaces
Variants

std:: binary_search

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
binary_search
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Definido en el 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 verifica utilizando operator < :

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

Si se satisface alguna de las siguientes condiciones, el comportamiento es indefinido:

  • 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 verifica utilizando comp :
Si ! bool ( comp ( * iter, value ) ) && ! bool ( comp ( value, * iter ) ) es true para algún iterador iter en [ first , last ) , retorna true . De lo contrario retorna false .
Si se satisface cualquiera de las siguientes condiciones, el comportamiento es indefinido:
  • 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 ) ) .

Contenidos

Parámetros

first, last - el par de iteradores que define el rango particionado de elementos a examinar
value - valor contra el cual comparar los elementos
comp - predicado binario que retorna ​ true si el primer argumento está ordenado antes del segundo.

La firma de la función predicado debe ser equivalente a lo siguiente:

bool pred ( const Type1 & a, const Type2 & b ) ;

Aunque la firma no necesita tener const & , la función no debe modificar los objetos pasados y debe poder aceptar todos los valores de tipo (posiblemente const) Type1 y Type2 independientemente de la categoría de valor (por lo tanto, Type1 & no está permitido , ni tampoco Type1 a menos que para Type1 un movimiento sea equivalente a una copia (desde C++11) ).
Los tipos Type1 y Type2 deben ser tales que un objeto de tipo T pueda convertirse implícitamente a ambos Type1 y Type2 , y un objeto de tipo ForwardIt pueda ser desreferenciado y luego convertido implícitamente a ambos Type1 y Type2 . ​

Requisitos de tipo
-
ForwardIt debe cumplir con los requisitos de LegacyForwardIterator .
-
Compare debe cumplir con los requisitos de BinaryPredicate . No se requiere que satisfaga Compare .

Valor de retorno

true si se encuentra un elemento equivalente a value , false en caso contrario.

Complejidad

Dado N como std:: distance ( first, last ) :

1) Como máximo log 2 (N)+O(1) comparaciones con value usando operator < (until C++20) std:: less { } (since C++20) .
2) Como máximo log 2 (N)+O(1) aplicaciones del comparador comp .

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

Notas

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

std::binary_search solo verifica si existe un elemento equivalente. Para obtener un iterador a ese elemento (si existe), std::lower_bound debería utilizarse en su lugar.

Macro de prueba de características Valor Std Característica
__cpp_lib_algorithm_default_value_type 202403 (C++26) Inicialización de lista para algoritmos ( 1,2 )

Implementación posible

Consulte 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

Ejecutar este código 
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>
int main()
{
    const auto haystack = {1, 3, 4, 5, 9};
    for (const auto needle : {1, 2, 3})
    {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle))
            std::cout << "Found " << needle << '\n';
        else
            std::cout << "Not found!\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: 

Searching for 1
Found 1
Searching for 2
Not found!
Searching for 3
Found 3

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

DR Aplicado a Comportamiento publicado Comportamiento correcto
LWG 270 C++98 Compare se requería que cumpliera con Compare y T se requería
que fuera LessThanComparable (se requería ordenamiento débil estricto) 		solo se requiere una partición;
se permiten comparaciones heterogéneas
LWG 787 C++98 se permitían como máximo log 2 (N)+2 comparaciones corregido a log 2 (N)+O(1)

Véase también

devuelve el rango de elementos que coinciden con una clave específica
(plantilla de función)
devuelve un iterador al primer elemento no menor que el valor dado
(plantilla de función)
devuelve un iterador al primer elemento mayor que cierto valor
(plantilla de función)
(C++20)
determina si un elemento existe en un rango parcialmente ordenado
(objeto función de algoritmo)