Implementar la Búsqueda Lineal en Arreglos
En este paso, aprenderás cómo implementar un algoritmo de Búsqueda Lineal en C++. La Búsqueda Lineal es un método simple para encontrar un elemento en un arreglo verificando cada elemento secuencialmente hasta que se encuentra el objetivo o se alcanza el final del arreglo.
Abre el WebIDE y crea un nuevo archivo llamado linear_search.cpp
en el directorio ~/project
:
touch ~/project/linear_search.cpp
Agrega el siguiente código al archivo linear_search.cpp
:
#include <iostream>
int linearSearch(int arr[], int size, int target) {
// Iterar a través de cada elemento en el arreglo
for (int i = 0; i < size; i++) {
// Verificar si el elemento actual coincide con el objetivo
if (arr[i] == target) {
return i; // Devolver el índice si se encuentra
}
}
return -1; // Devolver -1 si el objetivo no se encuentra
}
int main() {
// Crear un arreglo de calificaciones de estudiantes
int scores[] = {85, 92, 78, 95, 88, 76, 90};
int size = sizeof(scores) / sizeof(scores[0]);
// Calificación objetivo a buscar
int targetScore = 78;
// Realizar la búsqueda lineal
int result = linearSearch(scores, size, targetScore);
// Mostrar los resultados de la búsqueda
if (result!= -1) {
std::cout << "Calificación objetivo " << targetScore
<< " encontrada en el índice " << result << std::endl;
} else {
std::cout << "Calificación objetivo " << targetScore
<< " no encontrada en el arreglo" << std::endl;
}
// Intentar otra búsqueda
int missingScore = 100;
result = linearSearch(scores, size, missingScore);
if (result!= -1) {
std::cout << "Calificación " << missingScore
<< " encontrada en el índice " << result << std::endl;
} else {
std::cout << "Calificación " << missingScore
<< " no encontrada en el arreglo" << std::endl;
}
return 0;
}
Conceptos clave de la Búsqueda Lineal:
- Verifica cada elemento del arreglo secuencialmente
- Devuelve el índice del objetivo si se encuentra
- Devuelve -1 si el objetivo no está en el arreglo
- Complejidad temporal: O(n) - tiempo lineal
- Es simple y funciona para arreglos no ordenados
Compila y ejecuta el programa:
g++ linear_search.cpp -o linear_search
./linear_search
Ejemplo de salida:
Calificación objetivo 78 encontrada en el índice 2
Calificación 100 no encontrada en el arreglo
Notas importantes sobre la búsqueda:
- La Búsqueda Lineal es sencilla pero ineficiente para arreglos grandes
- Es adecuada para arreglos pequeños o colecciones no ordenadas
- Existen algoritmos de búsqueda más eficientes para arreglos ordenados