Apuntes DAM
Volver al inicio

Búsqueda lineal

AlgoritmosBúsquedaNivel básicoTambién: búsqueda secuencial, linear search

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.

De 1 a 16 enteros
  • 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

  1. Empezar por el principio. Un índice i recorre las posiciones desde 0.
  2. Comparar. Si a[i] es lo que se busca (o cumple la condición), se devuelve i y se termina.
  3. Avanzar. Si no, se pasa a i + 1.
  4. 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.

Java
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}

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).

Java
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 algo

Traza: buscar 5 en {7, 3, 9, 1, 12, 5, 8, 4}

ia[i]¿Es el 5?
07distinto, sigue
13distinto, sigue
29distinto, sigue
31distinto, sigue
412distinto, sigue
55¡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)
10010071
1.000.0001.000.000201
1.000.000.0001.000.000.000301

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.

0102030405015101520tamaño de la entrada (n)operacionesO(n!)O(2ⁿ)O(n²)O(n log n)O(1)O(log n)O(n)
  • 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; in y index en Python; includes y find en JavaScript.
  • Un SELECT ... WHERE sobre una columna sin índice hace una búsqueda lineal por toda la tabla (full scan): por eso se crean índices.
  • grep busca 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 -1 dentro del bucle en el else: 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 de equals: 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: «…».
☕JavaBuscar en la agendaFácil

Ejemplo

Entrada (lo que se escribe por teclado)
Ana 612345678
Andrés 699111222
Luis 655000111
? an
? lu
Salida esperada
Ana: 612345678
Andrés: 699111222
Luis: 655000111
⏳
Test oculto #3
⏳
Test oculto #4
0/4 tests pasados · pulsa un test para ver su entrada y su salida esperada
Ver la solución explicada
java
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 7 y Sin repetir: 1 9 (o ninguno).
  • Errores: No hay números y Número no válido: «x».
☕JavaRepetidos sin ordenarMedio

Ejemplo

Entrada (lo que se escribe por teclado)
4 7 4 1 7 7 9
Salida esperada
Repetidos: 4 7
Sin repetir: 1 9
⏳
Test oculto #3
⏳
Test oculto #4
⏳
Test oculto #5
0/5 tests pasados · pulsa un test para ver su entrada y su salida esperada
Ver la solución explicada
java
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 aciertos

Elige 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. 1.¿Qué necesita la búsqueda lineal que estén los datos?

  2. 2.¿Cuántas comparaciones hace en el peor caso con n elementos?

  3. 3.¿Qué error tiene este bucle? for (...) { if (a[i] == x) return i; else return -1; }

  4. 4.Vas a buscar 10.000 veces en el mismo array de un millón de datos. ¿Qué conviene?

  5. 5.¿Cuál de estos recorridos NO puede parar antes de llegar al final?

Relacionado