std::binary_search
| Definido en el archivo de encabezado <algorithm>
|
||
| (1) | ||
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, |
(constexpr desde C++20) (hasta C++26) |
|
| template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > |
(desde C++26) | |
| (2) | ||
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, |
(constexpr desde C++20) (hasta C++26) |
|
| template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, |
(desde C++26) | |
Comprueba si un elemento equivalente a value aparece dentro del rango particionado [first, last).
|
Si !bool(*iter < value) && !bool(value < *iter) es true para algún iterador iter en Si se cumple alguna de las siguientes condiciones, el comportamiento no está definido:
|
(hasta C++20) |
|
Equivalente a std::binary_search(first, last, value, std::less{}). |
(desde C++20) |
[first, last), devuelve true. De lo contrario devuelve false.- 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)).
Contenido |
[editar] 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) |
| Requisitos de tipo | ||
-ForwardIt debe satisfacer los requisitos de ForwardIterator.
| ||
-Compare debe satisfacer los requisitos de BinaryPredicate. No se requiere que satisfaga a Compare.
| ||
[editar] Valor de retorno
true si se encuentra un elemento equivalente a value, false de lo contrario.
[editar] Complejidad
Dada N como std::distance(first, last):
2(N)+O(1) comparaciones con value usando operator< (hasta C++20)std::less{} (desde C++20).
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 N.
[editar] 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) |
[editar] 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))); } |
[editar] Ejemplo
#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
[editar] 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 log 2(N)+2. |
Se corrigió a log 2(N)+O(1). |
[editar] Véase también
| Devuelve el rango de los 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 un valor determinado. (plantilla de función) | |
| (C++20) |
Determina si un elemento existe en un cierto rango. (niebloid) |
