Búsqueda lineal
Última actualización
La búsqueda lineal (también llamada búsqueda secuencial) es el algoritmo de búsqueda más simple: empieza en el primer elemento y compara cada uno con el objetivo hasta encontrar una coincidencia o quedarte sin elementos. No hace ninguna suposición sobre los datos: el arreglo puede estar desordenado, y los elementos pueden ser cualquier cosa que se pueda comparar por igualdad.
La animación de arriba resalta cada comparación mientras el recorrido avanza de izquierda a derecha y se detiene en cuanto aparece el objetivo. Su simplicidad tiene un costo en velocidad: en el peor caso se revisa cada elemento, por lo que se ejecuta en O(n). Cuando los datos están ordenados, la búsqueda binaria encuentra la misma respuesta en O(log n), y si primero necesitas datos ordenados, mira el merge sort.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(1) | El primer elemento es el objetivo. |
| Caso promedio | O(n) | En promedio se revisa la mitad de los elementos antes de un acierto. |
| Peor caso | O(n) | El objetivo es el último, o no está presente en absoluto. |
| Espacio | O(1) | Solo se guarda el índice actual. |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Empieza en el índice 0, el primer elemento del arreglo. |
| 2 | Compara el elemento actual con el valor objetivo. |
| 3 | Si son iguales, devuelve el índice actual (encontrado). |
| 4 | Si no, avanza una posición a la derecha y repite. |
| 5 | Si se llega al final del arreglo sin una coincidencia, el objetivo no está presente (devuelve -1). |
Ejemplo resuelto
Buscando 5 en [7, 3, 9, 1, 5, 8, 2]:
| Comparación | Índice | Elemento | Resultado |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5: sigue recorriendo. |
| 2 | 1 | 3 | 3 ≠ 5: sigue recorriendo. |
| 3 | 2 | 9 | 9 ≠ 5: sigue recorriendo. |
| 4 | 3 | 1 | 1 ≠ 5: sigue recorriendo. |
| 5 | 4 | 5 | 5 = 5: encontrado en el índice 4. |
Cuándo usar la búsqueda lineal
| Úsala cuando | Evítala cuando |
|---|---|
| Los datos están desordenados o cambian constantemente | Los datos están ordenados, porque la búsqueda binaria es exponencialmente más rápida |
| La colección es pequeña, así que gana la simplicidad | El conjunto de datos es grande y se busca repetidamente |
| Solo tienes acceso secuencial (flujos, listas enlazadas) | Puedes permitirte un índice o una tabla hash para búsquedas en O(1) |
Código de Linear Search
Una implementación limpia y ejecutable de Linear Search en Python, JavaScript, Java, C++, C, Pseudocode. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Linear Search en Python
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Código de Linear Search en JavaScript
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Código de Linear Search en Java
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Código de Linear Search en C++
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Código de Linear Search en C
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Código de Linear Search en Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Preguntas frecuentes sobre la búsqueda lineal
¿Cuál es la complejidad temporal de la búsqueda lineal?
O(n) en los casos promedio y peor (el recorrido puede tener que visitar cada elemento) y O(1) en el mejor caso, cuando el primer elemento es el objetivo. Usa O(1) de espacio adicional.¿La búsqueda lineal necesita datos ordenados?
No, esa es su principal ventaja. La búsqueda lineal funciona con datos completamente desordenados porque comprueba la igualdad de cada elemento; el orden nunca importa. La búsqueda binaria, en cambio, solo funciona con arreglos ordenados.
¿Cuándo es mejor la búsqueda lineal que la búsqueda binaria?
Cuando los datos están desordenados y se buscan una sola vez (ordenar primero costaría
O(n log n)), cuando la colección es diminuta, o cuando solo tienes acceso secuencial, como un flujo o una lista enlazada. Para búsquedas repetidas en arreglos ordenados, gana la búsqueda binaria.¿La búsqueda lineal es lo mismo que la búsqueda secuencial?
Sí, los dos nombres describen el mismo algoritmo: recorrer los elementos en secuencia hasta encontrar el objetivo o llegar al final de la colección.
¿Cuántas comparaciones hace la búsqueda lineal en promedio?
Si el objetivo está presente y tiene la misma probabilidad de estar en cualquier lugar, unas
n/2 comparaciones en promedio; si el objetivo no está, exactamente n. Ese crecimiento lineal es la razón por la que se llama búsqueda lineal.Recursos relacionados
Más visualizaciones
