HOWTO · C++
Búsqueda binaria C++ STL
Este tutorial demuestra cómo utilizar el algoritmo de búsqueda binaria de la biblioteca de plantillas estándar de C++.
En esta página
Usa std::binary_search cuando necesites saber si un valor aparece en un rango ordenado. Devuelve un resultado booleano de pertenencia; no devuelve el iterador coincidente ni la cantidad de valores coincidentes. La función sirve para un vector, un array u otro rango con iteradores adecuados, siempre que se cumplan los requisitos de ordenación.
Comprender los requisitos de std::binary_search
El rango de búsqueda debe estar particionado según la comparación que se utiliza en la búsqueda. En el uso habitual, esto significa que los elementos están ordenados de forma ascendente con el mismo criterio que la comparación predeterminada. Si el rango no está ordenado de esa manera, el resultado no permite determinar de forma fiable si el valor está presente. Ordenar el rango y luego cambiar o modificar parcialmente sus elementos también puede invalidar esta precondición.
El par de iteradores define un rango semiabierto, [first, last): first apunta al primer elemento que se considera, mientras que last apunta a una posición después del último elemento y queda excluido. Pasar container.begin() y container.end() busca en todo el contenedor. Un rango vacío es válido e indica que no hay coincidencias; un rango de un elemento incluye ese elemento cuando first apunta a él y last va después.
El resultado es true cuando hay un elemento equivalente según el criterio de ordenación, y false en caso contrario. Si necesitas obtener una posición, usa una operación como std::lower_bound y comprueba que el iterador devuelto no sea last y que el valor sea equivalente. std::binary_search por sí sola no permite saber cuál de los elementos duplicados coincidió.
Usar std::binary_search con un rango ordenado
Incluye <algorithm> para la función, <iostream> para la salida y <vector> para este contenedor. El siguiente programa completo comprueba un valor presente y otro ausente. Muestra directamente el resultado booleano para que ambos casos sean visibles sin depender de un iterador. Las etiquetas y la salida visibles del ejemplo permanecen en inglés, tal como aparecen en los bloques inalterados.
Ejecuta este ejemplo:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{2, 4, 6, 8, 10};
const bool has_six = std::binary_search(values.begin(), values.end(), 6);
const bool has_seven = std::binary_search(values.begin(), values.end(), 7);
std::cout << std::boolalpha
<< "6 found: " << has_six << '\n'
<< "7 found: " << has_seven << '\n';
}
6 found: true
7 found: false
El vector ya está ordenado y cada llamada recibe el rango completo de sus iteradores. Cambia cualquiera de los valores buscados para adaptar el ejemplo; mantén el vector en el mismo orden que requiere la búsqueda. La función no ordena el rango por ti. Las etiquetas y la salida visibles permanecen en inglés.
Buscar con un comparador personalizado
Para un tipo definido por el usuario, pasa un comparador que establezca el criterio de ordenación del rango. Ordena el rango con ese mismo comparador antes de buscar. En este ejemplo, los registros se ordenan por edad y se considera que el valor está presente si hay un registro con esa edad. El nombre no forma parte del criterio de identidad de este comparador.
El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.
#include <algorithm>
#include <string>
#include <vector>
struct Person {
std::string name;
int age;
};
int main() {
const auto by_age = [](const Person& left, const Person& right) {
return left.age < right.age;
};
std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
std::sort(people.begin(), people.end(), by_age);
const Person target{"", 25};
const bool found = std::binary_search(
people.begin(), people.end(), target, by_age);
return found ? 0 : 1;
}
El comparador compara valores, no iteradores. Debe establecer el orden utilizado para organizar el rango y admitir comparaciones compatibles entre los elementos del rango y el valor buscado. Aquí, dos registros con la misma edad son equivalentes para esta búsqueda, aunque sus nombres sean distintos. Si la aplicación necesita distinguirlos, incluye los campos que los diferencian en el criterio de ordenación o usa otra estrategia de búsqueda.
Evitar errores comunes en la búsqueda binaria
- Buscar datos desordenados: ordena primero el rango. Ordenar por una clave y buscar con otro criterio no satisface el requisito de búsqueda.
- Tratar
lastcomo un elemento:lastqueda excluido. Usacontainer.end()para buscar en todo el contenedor; no lo desreferencies. - Esperar un iterador: el tipo de retorno es booleano. Usa
std::lower_boundcuando necesites una ubicación y comprueba el resultado antes de desreferenciarlo. - Usar un comparador incompatible: la ordenación y la búsqueda deben coincidir en el criterio y la equivalencia. Si un comparador considera equivalentes dos registros, la búsqueda determina la pertenencia según esa regla, no según todos los campos del registro.
Estas comprobaciones permiten interpretar correctamente el resultado de la función. La biblioteca realiza la búsqueda, pero no puede detectar que el rango se preparó con otro criterio de ordenación o que el comparador no corresponde a los datos.