Búsqueda lineal
Recorre los elementos uno a uno hasta encontrar el que se busca (o acabar). No necesita que los datos estén ordenados y sirve para cualquier condición; cuesta O(n).
Visualízalo paso a paso
Cambia los datos, dale a reproducir y sigue cada paso en el dibujo, en la línea de Java que se ejecuta y en sus variables.
Búsqueda lineal
Escribe un array (no hace falta que esté ordenado) y el valor que buscas.
- sin mirar
Paso 1
Buscamos el 5 mirando los elementos uno a uno, desde el principio. No hace falta que estén ordenados.
1static int buscar(int[] a, int x) {
2 for (int i = 0; i < a.length; i++) {
3 if (a[i] == x) return i;
4 }
5 return -1;
6}Variables
- x
- 5
Atajos con el foco dentro del visualizador: ← → paso a paso, Espacio reproducir o pausar, Inicio/Fin ir al principio o al final.
La idea
La búsqueda lineal (o secuencial) es la forma más directa de buscar: mirar el primer elemento, luego el segundo, luego el tercero… hasta encontrar el que buscamos o llegar al final sin encontrarlo.
Su gran ventaja es que no pide nada a los datos: funciona con arrays desordenados, con listas enlazadas, con ficheros que se leen línea a línea y con cualquier condición, no solo «igual a x» («la primera nota aprobada», «el primer cliente de Sevilla»).
Su coste depende de dónde esté el elemento: si está el primero, una comparación; si está el último o no está, n. De media, si está, mira la mitad. Por eso es O(n): con un millón de datos, hasta un millón de comparaciones.
Hay que distinguir dos tipos de recorrido: los que pueden parar en cuanto encuentran algo (buscar, comprobar si existe, el primero que cumple) y los que tienen que mirarlos todos sí o sí (contar, sumar, buscar el máximo). Salir con return o break en cuanto se puede es la diferencia entre un buen recorrido y uno que trabaja de más.
Cuándo usarlo
- Datos sin ordenar en los que se busca pocas veces.
- Pocos datos (decenas o cientos): es tan rápida como cualquier otra y más sencilla.
- Cuando se busca por una condición cualquiera, no por un valor exacto.
- Estructuras sin acceso directo, como listas enlazadas o datos que llegan en un flujo.
Cuándo no
- Muchas búsquedas sobre los mismos datos: ordenar una vez y usar búsqueda binaria, o meterlos en un
HashSet/HashMap(O(1)). - Buscar dentro de un bucle que recorre los mismos datos: un doble recorrido es O(n²) y suele haber una forma mejor.
Paso a paso
- Empezar por el principio. Un índice
irecorre las posiciones desde 0. - Comparar. Si
a[i]es lo que se busca (o cumple la condición), se devuelveiy se termina. - Avanzar. Si no, se pasa a
i + 1. - No está. Si se llega al final sin encontrarlo, se devuelve un valor que no puede ser una posición:
-1.
El código
Buscar, contar y el primero que cumple
Tres recorridos lineales: dos pueden parar en cuanto encuentran, el de contar tiene que mirarlos todos.
1public class Main {
2 /** Posición de la primera aparición de x, o -1. */
3 static int buscar(int[] a, int x) {
4 for (int i = 0; i < a.length; i++)
5 if (a[i] == x) return i; // en cuanto aparece, no hace falta seguir
6 return -1;
7 }
8
9 /** Cuántas veces aparece x: aquí sí hay que mirarlos todos. */
10 static int contar(int[] a, int x) {
11 int n = 0;
12 for (int v : a) if (v == x) n++;
13 return n;
14 }
15
16 /** Posición del primero que cumple una condición: la primera nota aprobada. */
17 static int primerAprobado(int[] notas) {
18 for (int i = 0; i < notas.length; i++)
19 if (notas[i] >= 5) return i;
20 return -1;
21 }
22
23 public static void main(String[] args) {
24 int[] notas = {3, 4, 7, 5, 4, 9, 4};
25 System.out.println("¿Dónde está el 5? En la posición " + buscar(notas, 5));
26 System.out.println("¿Dónde está el 10? " + buscar(notas, 10) + " (no está)");
27 System.out.println("¿Cuántos 4 hay? " + contar(notas, 4));
28 System.out.println("Primera nota aprobada: posición " + primerAprobado(notas));
29 }
30}def buscar(a, x):
"""Posición de la primera aparición de x, o -1."""
for i in range(len(a)):
if a[i] == x:
return i # en cuanto aparece, no hace falta seguir
return -1
def contar(a, x):
"""Cuántas veces aparece x: aquí sí hay que mirarlos todos."""
n = 0
for v in a:
if v == x:
n += 1
return n
def primer_aprobado(notas):
"""Posición del primero que cumple una condición: la primera nota aprobada."""
for i, n in enumerate(notas):
if n >= 5:
return i
return -1
notas = [3, 4, 7, 5, 4, 9, 4]
print("¿Dónde está el 5? En la posición", buscar(notas, 5))
print("¿Dónde está el 10?", buscar(notas, 10), "(no está)")
print("¿Cuántos 4 hay?", contar(notas, 4))
print("Primera nota aprobada: posición", primer_aprobado(notas))/** Posición de la primera aparición de x, o -1. */
function buscar(a, x) {
for (let i = 0; i < a.length; i++)
if (a[i] === x) return i; // en cuanto aparece, no hace falta seguir
return -1;
}
/** Cuántas veces aparece x: aquí sí hay que mirarlos todos. */
function contar(a, x) {
let n = 0;
for (const v of a) if (v === x) n++;
return n;
}
/** Posición del primero que cumple una condición: la primera nota aprobada. */
function primerAprobado(notas) {
for (let i = 0; i < notas.length; i++)
if (notas[i] >= 5) return i;
return -1;
}
const notas = [3, 4, 7, 5, 4, 9, 4];
console.log("¿Dónde está el 5? En la posición " + buscar(notas, 5));
console.log("¿Dónde está el 10? " + buscar(notas, 10) + " (no está)");
console.log("¿Cuántos 4 hay? " + contar(notas, 4));
console.log("Primera nota aprobada: posición " + primerAprobado(notas));using System;
class Program {
// Posición de la primera aparición de x, o -1.
static int Buscar(int[] a, int x) {
for (int i = 0; i < a.Length; i++)
if (a[i] == x) return i; // en cuanto aparece, no hace falta seguir
return -1;
}
// Cuántas veces aparece x: aquí sí hay que mirarlos todos.
static int Contar(int[] a, int x) {
int n = 0;
foreach (int v in a) if (v == x) n++;
return n;
}
// Posición del primero que cumple una condición: la primera nota aprobada.
static int PrimerAprobado(int[] notas) {
for (int i = 0; i < notas.Length; i++)
if (notas[i] >= 5) return i;
return -1;
}
static void Main() {
int[] notas = { 3, 4, 7, 5, 4, 9, 4 };
Console.WriteLine("¿Dónde está el 5? En la posición " + Buscar(notas, 5));
Console.WriteLine("¿Dónde está el 10? " + Buscar(notas, 10) + " (no está)");
Console.WriteLine("¿Cuántos 4 hay? " + Contar(notas, 4));
Console.WriteLine("Primera nota aprobada: posición " + PrimerAprobado(notas));
}
}<?php
/** Posición de la primera aparición de $x, o -1. */
function buscar(array $a, int $x): int {
for ($i = 0; $i < count($a); $i++)
if ($a[$i] === $x) return $i; // en cuanto aparece, no hace falta seguir
return -1;
}
/** Cuántas veces aparece $x: aquí sí hay que mirarlos todos. */
function contar(array $a, int $x): int {
$n = 0;
foreach ($a as $v) if ($v === $x) $n++;
return $n;
}
/** Posición del primero que cumple una condición: la primera nota aprobada. */
function primerAprobado(array $notas): int {
foreach ($notas as $i => $n) if ($n >= 5) return $i;
return -1;
}
$notas = [3, 4, 7, 5, 4, 9, 4];
echo "¿Dónde está el 5? En la posición " . buscar($notas, 5) . "\n";
echo "¿Dónde está el 10? " . buscar($notas, 10) . " (no está)\n";
echo "¿Cuántos 4 hay? " . contar($notas, 4) . "\n";
echo "Primera nota aprobada: posición " . primerAprobado($notas) . "\n";Salida al ejecutarlo (la misma en los 5 lenguajes)
¿Dónde está el 5? En la posición 3 ¿Dónde está el 10? -1 (no está) ¿Cuántos 4 hay? 3 Primera nota aprobada: posición 2
Las búsquedas de la biblioteca
indexOf, contains o find son búsquedas lineales ya escritas: cómodas, pero igual de O(n).
1// Las bibliotecas traen la búsqueda lineal hecha (y sigue siendo O(n))
2List<String> nombres = List.of("Ana", "Luis", "Eva");
3int pos = nombres.indexOf("Eva"); // 2 (-1 si no está)
4boolean esta = nombres.contains("Luis"); // true
5Optional<String> conE = nombres.stream()
6 .filter(n -> n.startsWith("E")).findFirst(); // el primero que cumple algonombres = ["Ana", "Luis", "Eva"]
pos = nombres.index("Eva") # 2 (lanza ValueError si no está)
esta = "Luis" in nombres # True
con_e = next((n for n in nombres if n.startswith("E")), None) # el primero que cumple algoconst nombres = ["Ana", "Luis", "Eva"];
const pos = nombres.indexOf("Eva"); // 2 (-1 si no está)
const esta = nombres.includes("Luis"); // true
const conE = nombres.find((n) => n.startsWith("E")); // el primero que cumple algo (o undefined)var nombres = new List<string> { "Ana", "Luis", "Eva" };
int pos = nombres.IndexOf("Eva"); // 2 (-1 si no está)
bool esta = nombres.Contains("Luis"); // true
string? conE = nombres.FirstOrDefault(n => n.StartsWith("E")); // el primero que cumple algo (o null)$nombres = ["Ana", "Luis", "Eva"];
$pos = array_search("Eva", $nombres, true); // 2 (false si no está)
$esta = in_array("Luis", $nombres, true); // true
$conE = array_values(array_filter($nombres, fn($n) => str_starts_with($n, "E")))[0] ?? null;Traza: buscar 5 en {7, 3, 9, 1, 12, 5, 8, 4}
| i | a[i] | ¿Es el 5? |
|---|---|---|
| 0 | 7 | distinto, sigue |
| 1 | 3 | distinto, sigue |
| 2 | 9 | distinto, sigue |
| 3 | 1 | distinto, sigue |
| 4 | 12 | distinto, sigue |
| 5 | 5 | ¡igual! |
Seis comparaciones; las dos últimas posiciones ya no hace falta mirarlas.
Complejidad
| Datos (n) | Búsqueda lineal (peor caso) | Búsqueda binaria (datos ordenados) | HashSet (de media) |
|---|---|---|---|
| 100 | 100 | 7 | 1 |
| 1.000.000 | 1.000.000 | 20 | 1 |
| 1.000.000.000 | 1.000.000.000 | 30 | 1 |
O(1) en el mejor caso, O(n) en el medio y en el peor. Memoria extra: O(1). Si se va a buscar muchas veces, compensa ordenar o meter los datos en una tabla hash.
- Mejor caso: O(1)
- Caso medio: O(n)
- Peor caso: O(n)
El mejor caso es que esté el primero; de media mira la mitad; si no está, todos. Las curvas grises son las demás clases, para comparar.
En la práctica
indexOf,contains,stream().filter(...).findFirst()en Java;inyindexen Python;includesyfinden JavaScript.- Un
SELECT ... WHEREsobre una columna sin índice hace una búsqueda lineal por toda la tabla (full scan): por eso se crean índices. grepbusca un texto recorriendo los ficheros línea a línea.- Con pocos elementos (menos de unas decenas) es tan rápida como cualquier otra y es lo que se usa.
Errores típicos
- Devolver
-1dentro del bucle en elelse: en cuanto el primero no coincide, devuelve «no está» sin mirar los demás. - Seguir recorriendo después de encontrarlo cuando solo se quería saber si estaba: trabajo inútil.
- Comparar textos con
==en vez deequals: compara referencias, no contenidos. - Buscar dentro de otro bucle sobre los mismos datos sin darse cuenta de que es O(n²).
- Usar una variable «encontrado» y no salir del bucle, y luego devolver la posición de la última aparición en vez de la primera.
Ejercicios
Cada ejercicio se corrige solo con sus pruebas (algunas ocultas). Escribe tu solución en el editor y pulsa Ejecutar o Comprobar; la solución explicada está debajo, por si te atascas.
1. Buscar en la agenda
Cada línea de la entrada es un contacto (nombre teléfono, el teléfono de 9 cifras) o una búsqueda (? prefijo). Una búsqueda muestra todos los contactos guardados hasta ese momento cuyo nombre empieza por el prefijo, sin distinguir mayúsculas, en el orden en que se guardaron. Completa buscar.
- Contacto:
Ana 612345678. Búsqueda:? an. - Por cada resultado:
Ana: 612345678; si no hay ninguno,Nadie empieza por «an». - Una línea que no es ninguna de las dos cosas:
Línea no válida: «…».
Ejemplo
Ana 612345678 Andrés 699111222 Luis 655000111 ? an ? lu
Ana: 612345678 Andrés: 699111222 Luis: 655000111
Ver la solución explicada
1import java.util.*;
2
3public class Main {
4 record Contacto(String nombre, String telefono) { }
5
6 /** Los contactos cuyo nombre empieza por el prefijo (sin distinguir mayúsculas), en el orden de la agenda. */
7 static List<Contacto> buscar(List<Contacto> agenda, String prefijo) {
8 List<Contacto> r = new ArrayList<>();
9 String p = prefijo.toLowerCase();
10 for (Contacto c : agenda)
11 if (c.nombre().toLowerCase().startsWith(p)) r.add(c);
12 return r;
13 }
14
15 public static void main(String[] args) {
16 Scanner sc = new Scanner(System.in);
17 List<Contacto> agenda = new ArrayList<>();
18 while (sc.hasNextLine()) {
19 String linea = sc.nextLine().trim();
20 if (linea.isEmpty()) continue;
21 if (linea.startsWith("? ")) {
22 String prefijo = linea.substring(2).trim();
23 List<Contacto> r = buscar(agenda, prefijo);
24 if (r.isEmpty()) System.out.println("Nadie empieza por «" + prefijo + "»");
25 for (Contacto c : r) System.out.println(c.nombre() + ": " + c.telefono());
26 } else {
27 String[] p = linea.split("\\s+");
28 if (p.length == 2 && p[1].matches("\\d{9}")) agenda.add(new Contacto(p[0], p[1]));
29 else System.out.println("Línea no válida: «" + linea + "»");
30 }
31 }
32 }
33}Es una búsqueda lineal que no para en el primero, porque se quieren todos los que cumplen: un filtro. Cada búsqueda cuesta O(n).
Para una agenda de millones de contactos se ordenarían los nombres y se buscaría el prefijo con búsqueda binaria, o se usaría un árbol de prefijos (trie).
2. Repetidos sin ordenar
Lee una línea de enteros y escribe, en el orden en que aparecen por primera vez, los que están repetidos y los que aparecen una sola vez. Sin ordenar ni usar colecciones: para cada posición, una búsqueda lineal hacia atrás dice si ya había salido y otra hacia delante si vuelve a salir. Completa apareceAntes y apareceDespues.
- Entrada:
4 7 4 1 7 7 9. - Salida:
Repetidos: 4 7ySin repetir: 1 9(oninguno). - Errores:
No hay númerosyNúmero no válido: «x».
Ejemplo
4 7 4 1 7 7 9
Repetidos: 4 7 Sin repetir: 1 9
Ver la solución explicada
1import java.util.*;
2
3public class Main {
4 /** ¿Aparece a[i] en alguna posición anterior a i? (Una búsqueda lineal en a[0..i-1].) */
5 static boolean apareceAntes(int[] a, int i) {
6 for (int j = 0; j < i; j++)
7 if (a[j] == a[i]) return true;
8 return false;
9 }
10
11 /** ¿Aparece a[i] en alguna posición posterior a i? */
12 static boolean apareceDespues(int[] a, int i) {
13 for (int j = i + 1; j < a.length; j++)
14 if (a[j] == a[i]) return true;
15 return false;
16 }
17
18 public static void main(String[] args) {
19 Scanner sc = new Scanner(System.in);
20 String linea = sc.hasNextLine() ? sc.nextLine().trim() : "";
21 if (linea.isEmpty()) {
22 System.out.println("No hay números");
23 return;
24 }
25 String[] t = linea.split("\\s+");
26 int[] a = new int[t.length];
27 for (int i = 0; i < t.length; i++) {
28 if (!t[i].matches("-?\\d{1,9}")) {
29 System.out.println("Número no válido: «" + t[i] + "»");
30 return;
31 }
32 a[i] = Integer.parseInt(t[i]);
33 }
34 StringJoiner repetidos = new StringJoiner(" "), unicos = new StringJoiner(" ");
35 for (int i = 0; i < a.length; i++) {
36 boolean antes = apareceAntes(a, i), despues = apareceDespues(a, i);
37 if (!antes && despues) repetidos.add(String.valueOf(a[i])); // primera aparición de un repetido
38 if (!antes && !despues) unicos.add(String.valueOf(a[i]));
39 }
40 System.out.println("Repetidos: " + (repetidos.length() == 0 ? "ninguno" : repetidos));
41 System.out.println("Sin repetir: " + (unicos.length() == 0 ? "ninguno" : unicos));
42 }
43}Cada posición hace dos búsquedas lineales: en total O(n²). Con 1.000 números son un millón de comparaciones; con un millón, un billón.
Con un HashMap que cuente apariciones se hace en una pasada, O(n): la búsqueda lineal anidada es justo el patrón que conviene reconocer para cambiarlo.
Test
Test: Búsqueda lineal
0/5 respondidas · 0 aciertosElige una respuesta en cada pregunta: verás al momento si es correcta y por qué. Con un 80 % de aciertos se da por superada.
1.¿Qué necesita la búsqueda lineal que estén los datos?
2.¿Cuántas comparaciones hace en el peor caso con n elementos?
3.¿Qué error tiene este bucle?
for (...) { if (a[i] == x) return i; else return -1; }4.Vas a buscar 10.000 veces en el mismo array de un millón de datos. ¿Qué conviene?
5.¿Cuál de estos recorridos NO puede parar antes de llegar al final?