Revisar uno tras otro
Búsqueda lineal: revisar a cada uno
Imagina que tienes 10 tarjetas boca abajo, numeradas del 1 al 10, mezcladas en un orden aleatorio.
Quieres encontrar la tarjeta con el número 7.
Giras las tarjetas una a una, de izquierda a derecha, hasta que la encuentras.
| Escenario | Volteados necesarios |
|----------|----------------------|
| Mejor caso | 1 vuelta (¡suerte en el primer intento!) |
| Peor caso | 10 vueltas (estaba la última tarjeta) |
| Promedio | alrededor de 5 vueltas |
Ahora imagina 100 tarjetas. Promedio: alrededor de 50 vueltas.
1,000 tarjetas? Promedio: alrededor de 500 vueltas.
¿Ves el patrón? Dobles las tarjetas, dobles el trabajo. El trabajo crece en una línea recta.
Los científicos de la computación llaman a esto búsqueda lineal - lineal significa que el trabajo crece como una línea: constante y predecible.
La búsqueda lineal funciona en cualquier lista, ordenada o no. Eso lo hace simple. Pero también puede ser lento.
¿Cuántos nombres?
Tienes una lista de nombres de 20 nombres escritos en orden aleatorio.
Necesitas encontrar el nombre Zoe.
Revisas los nombres una a una, desde la parte de arriba de la lista hacia abajo.
Cortar la lista por la mitad
Búsqueda binaria: Salta al medio
La búsqueda binaria tiene una regla: la lista debe estar ordenada primero.
Si tu lista de 20 nombres va de A a Z, puedes usar la búsqueda binaria.
Cómo funciona: abre en el nombre medio (nombre #10). Pregunta: ¿Zoe está antes o después de este nombre?
Z viene al final del alfabeto, así que Zoe está DESPUÉS del medio. Elimina la primera mitad. Ahora tienes solo nombres 11-20.
Revisa el medio de esos 10 nombres (nombre #15). Z está después de M, así que Zoe está después del nombre #15. Elimina los nombres 11-14. Ahora tienes nombres 16-20.
Sigue cortando por la mitad. Cada verificación elimina la mitad de los nombres restantes.
| Tamaño de la lista | Verificaciones máximas con búsqueda binaria |
|-----------|-------------------------------|
| 20 nombres | hasta 5 verificaciones |
| 1,000 nombres | hasta 10 verificaciones |
| 1,000,000 nombres | hasta 20 verificaciones |
Compara eso con la búsqueda lineal en 1,000,000 nombres: un promedio de 500,000 verificaciones.
La búsqueda binaria corta la lista por la mitad cada vez. Cortar por la mitad repetidamente llega a 1 muy rápidamente - eso es por qué se mantiene tan rápido.
Encontrar 'fig' en una lista ordenada
Aquí hay una lista ordenada de 8 palabras:
1. manzana 2. plátano 3. cereza 4. durazno 5. arándano maduro 6. higo 7. uva 8. melón
Quieres encontrar higo usando la búsqueda binaria.
Recuerda: verifica el medio, pregunta si tu objetivo está antes o después, luego corta la lista por la mitad.
Intercambiar vecinos en orden
Ordenamiento de burbujas: Comparar vecinos e intercambiar
El ordenamiento de burbujas ordena una lista comparando dos elementos adyacentes.
Si dos vecinos están desordenados — intercambiarlos.
Sigue haciendo pasadas a través de la lista hasta que ya no se necesitan intercambios.
Ejemplo: ordenar [5, 3, 8, 1]
Pasada 1:
- Comparar 5 y 3. 5 > 3, así que intercambiar → [3, 5, 8, 1]
- Comparar 5 y 8. 5 < 8, sin intercambio → [3, 5, 8, 1]
- Comparar 8 y 1. 8 > 1, así que intercambiar → [3, 5, 1, 8]
Pasada 2:
- Comparar 3 y 5. OK → [3, 5, 1, 8]
- Comparar 5 y 1. 5 > 1, intercambiar → [3, 1, 5, 8]
- Comparar 5 y 8. OK → [3, 1, 5, 8]
Pasada 3:
- Comparar 3 y 1. 3 > 1, intercambiar → [1, 3, 5, 8]
- Comparar 3 y 5. OK. Comparar 5 y 8. OK.
Hecho! [1, 3, 5, 8] ✓
Nota: el número más grande sube a la parte de abajo en cada pasada. Eso es cómo el ordenamiento de burbujas obtiene su nombre.
El ordenamiento de burbujas funciona. No es lo más rápido para listas grandes, pero es fácil de entender — perfecto para aprender.
Ordena [4, 2, 7, 1] con Ordenamiento de Burbujas
Ordena esta lista usando ordenamiento de burbujas: [4, 2, 7, 1]
Muestra la lista después de cada pasada. Cuenta cuántas pasadas toma para terminar.