close

Algoritmo de búsqueda lineal (Linear Search) en C++: explicación, ejemplo y código

El algoritmo de búsqueda lineal es un método simple que se utiliza para encontrar un elemento específico en una lista. Este algoritmo funciona comprobando secuencialmente cada elemento de la lista hasta que se encuentra el elemento deseado o se recorre toda la lista.

Cómo funciona

  1. Comience desde el primer elemento de la lista.
  2. Compare el elemento actual con el valor objetivo.
  3. Si el elemento actual es igual al valor objetivo, el algoritmo termina y devuelve la posición del elemento.
  4. Si no, continúe iterando a través de los elementos restantes de la lista.
  5. Si se recorre toda la lista sin encontrar el elemento de destino, el algoritmo devuelve un valor que indica que no se encuentra.

Ejemplo

Digamos que tenemos una lista de números enteros y queremos encontrar el número 34 en la lista.

Lista: {12, 45, 67, 89, 34, 56, 23, 90}

  1. Comience en el primer elemento: 12. No es el número deseado.
  2. Pasa al siguiente elemento: 45. No es el número deseado.
  3. Continúe con los elementos restantes: 67, 89, 34. El elemento 34 coincide con el número deseado.
  4. El algoritmo termina y devuelve la posición de 34, que es 4.

Código de ejemplo en C++ 

#include <iostream>  
#include <vector>  
  
int linearSearch(const std::vector<int>& arr, int target) {  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};  
    int target = 34;  
  
    int result = linearSearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

En el ejemplo dado, hemos usado la linearSearch función para encontrar el número 34 en la lista de enteros. El resultado será la posición 34 en la lista(las posiciones comienzan desde 0) o -1 si no se encuentra el número.