Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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.

Fuentes