Los algoritmos de búsqueda y conteo en la STL ([C++98]) permiten localizar elementos o cuantificar ocorrurencias dentro de un rango definido por dos iteradores. En lugar de implementar bucles manuales, utilizamos estas abstracciones para expresar la intención del código, lo que permite al compilador aplicar optimizaciones específicas y garantiza que el algoritmo sea lo más eficiente posible para el contenedor utilizado.
Básicamente, estos algoritmos operan bajo dos lógicas: la búsqueda lineal (recorrer uno a uno los elementos, con una complejidad de $O(n)$) y la búsqueda binaria (dividir el rango a la mitad repetidamente, con una complejidad de $O(\log n)$). La búsqueda binaria es extremadamente rápida, pero tiene un requisito estricto: el rango debe estar ordenado respecto al criterio de comparación. Si usas algoritmos de búsqueda binaria en un rango desordenado, entrarás en el terreno del comportamiento indefinido (undefined behavior), ya que el algoritmo simplemente “saltará” porciones del contenedor que debería contener el valor, devolviendo resultados erróneos o inconsistentes.
Debes usar búsqueda lineal (std::find, std::find_if) cuando el orden no está garantizado o el contenedor no soporta acceso aleatorio eficiente (como std::list). Debes usar búsqueda binaria (std::lower_bound, std::upper_bound) cuando el rendimiento sea crítico y los datos ya estén ordenados. Si necesitas contar cuántos elementos cumplen una condición, std::count_if es tu herramienta. Si intentas usar std::lower_bound en un vector desordenado, lo más probable es que el programa no falle de inmediato, pero el resultado será basura lógica, un error que puede ser extremadamente difícil de rastrear en sistemas complejos.
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <ranges> // C++20
struct Item {
int id;
std::string nombre;
// Necesario para algoritmos de búsqueda binaria en el objeto
bool operator<(const Item& other) const { return id < other.id; }
};
int main() {
// El contenedor debe estar ordenado por 'id' para la búsqueda binaria
std::vector<Item> inventario = {
{10, "Teclado"},
{20, "Ratón"},
{20, "Monitor"},
{30, "Cable"},
{40, "USB"}
};
// 1. std::find_if: Buscar por una condición (predicado)
auto it_nombre = std::find_if(inventario.begin(), inventario.end(),
[](const Item& i) { return i.nombre == "Monitor"; });
if (it_nombre != inventario.end()) {
std::cout << "Encontrado: " << it_nombre->nombre << "\n";
}
// 2. std::count_if: Contar elementos que cumplen un predicado
int caros = std::count_if(inventario.begin(), inventario.end(),
[](const Item& i) { return i.id > 25; });
std::cout << "Items con ID > 25: " << caros << "\n";
// 3. std::binary_search: Verificar existencia en rango ordenado
bool existe_20 = std::binary_search(inventario.begin(), inventario.end(), Item{20, ""});
std::cout << "¿Existe ID 20?: " << (existe_20 ? "Sí" : "No") << "\n";
// 4. std::lower_bound: Primer elemento >= valor
// Devuelve el primer elemento que no es menor que 20
auto lb = std::lower_bound(inventario.begin(), inventario.end(), Item{20, ""});
std::cout << "Lower bound de 20: " << lb->nombre << "\n";
// 5. std::upper_bound: Primer elemento > valor
// Devuelve el primer elemento estrictamente mayor que 20
auto ub = std::upper_bound(inventario.begin(), inventario.end(), Item{20, ""});
std::cout << "Upper bound de 20: " << ub->nombre << "\n";
// 6. std::equal_range: Retorna el par (lower_bound, upper_bound)
// Es ideal para obtener un sub-rango de elementos con la misma clave
auto [r_start, r_end] = std::equal_range(inventario.begin(), inventario.end(), Item{20, ""});
std::cout << "Elementos con ID 20: ";
for (auto it = r_start; it != r_end; ++it) {
std::cout << it->nombre << " ";
}
std::cout << "\n";
// 7. std::search: Buscar una sub-secuencia
std::vector<int> secuencia = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> patrón = {3, 4, 5};
auto sub_it = std::search(secuencia.begin(), secuencia.end(), patrón.begin(), patrón.end());
if (sub_it != secuencia.end()) {
std::cout << "Sub-secuencia encontrada en el índice: "
<< std::distance(secuencia.begin(), sub_it) << "\n";
}
return 0;
}
Desglose del ejemplo
En el código anterior, hemos manejado diferentes niveles de complejidad y lógica de búsqueda.
Cuando usamos std::find_if con la lambda [](const Item& i) { return i.nombre == "Monitor"; }, estamos realizando una búsqueda lineal. El algoritmo compara cada elemento hasta que la función devuelve true. Si llegamos al end() del vector, el iterador devuelto indica que no hubo coincidencia.
Para la búsqueda binaria, es vital entender la diferencia entre std::lower_bound y std::upper_bound. En nuestro std::vector<Item>, tenemos dos elementos con id == 20.
– std::lower_bound nos devuelve el iterador al primer elemento que no es menor que 20 (el primer “Ratón”).
– std::upper_bound nos devuelve el iterador al primer elemento que es estrictamente mayor que 20 (el “Cable”).
La función std::equal_range es una optimización de diseño: en lugar de llamar dos veces a funciones de búsqueda binaria (lo cual duplicaría el trabajo de comparación), devuelve un std::pair de iteradores que definen exactamente el rango de elementos que comparten la misma clave. En el ejemplo, gracias al structured binding [C++17], desestructuramos ese par directamente en r_start y r_end.
Finalmente, std::search no busca un valor escalar, sino un patrón. Es la base para implementaciones de búsqueda de sub-cadenas o sub-secuencias, comparando cada posición del rango principal con el rango patrón.
El error frecuente
El error más crítico y sutil ocurre al usar algoritmos de complejidad logarítmica como std::lower_bound o std::binary_search sobre un contenedor que no ha sido ordenado previamente bajo el mismo criterio de comparación.
std::vector<int> datos = {50, 10, 30, 20, 40}; // Desordenado
// ERROR: std::lower_bound asume que el rango está ordenado.
auto it = std::lower_bound(datos.begin(), datos.end(), 30);
// El resultado de 'it' es impredecible: puede ser el 30, o puede ser 50.
Si intentas depurar esto con std::cout, el programa no lanzará una excepción ni un error de segmentación; simplemente te dará un valor incorrecto. Esto es un fallo silencioso. Para detectar esto durante el desarrollo, puedes compilar con AddressSanitizer o usar herramientas de análisis estático, aunque la mejor defensa es asegurar la invariant: si el algoritmo requiere orden, el contenedor debe estar ordenado.
N° 71