CKTIS / C++
Búsqueda lineal
La búsqueda lineal comprueba elementos sucesivos sin exigir que los datos estén ordenados. En C++, std::find devuelve un iterador al primer elemento coincidente o el iterador de fin.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
std::find(first, last, value)La búsqueda lineal (linear search) comprueba elementos sucesivos hasta encontrar una coincidencia o agotar el rango. Los datos no tienen que estar ordenados.
Usa std::find(first, last, value) de <algorithm>. El rango [first, last) no incluye last. El resultado es un iterador al primer elemento que cumple *it == value, no un índice. Si no hay coincidencia, también en un rango vacío, el resultado es last; no lo desreferencies.
Para n elementos se necesitan como máximo n comparaciones: el coste en el peor caso es O(n). El ejemplo muestra duplicados y un valor que no aparece. La resta de iteradores da un índice basado en cero, porque std::array proporciona iteradores de acceso aleatorio.
El ejemplo está pensado para C++23. La página citada es un borrador de trabajo en evolución, no una publicación definitiva de C++23.
Ejemplos
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array<int, 5> values{8, 3, 6, 3, 9};
for (int target : {3, 7}) {
const auto it = std::find(values.begin(), values.end(), target);
std::cout << target << ": ";
if (it != values.end()) {
std::cout << "index " << (it - values.begin()) << '\n';
} else {
std::cout << "not found\n";
}
}
}
Resultado
3: index 1 7: not found
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.