Verificando Uno a la Vez
Búsqueda Lineal: Verifica Cada Uno
Imagina que tienes 10 tarjetas boca abajo, numeradas del 1 al 10, mezcladas en orden aleatorio.
Quieres encontrar la tarjeta con el número 7.
Das vuelta a las tarjetas una a la vez, de izquierda a derecha, hasta encontrarla.
| Escenario | Volteos Necesarios |
|---|---|
| Mejor caso | 1 volteo (¡intento afortunado!) |
| Peor caso | 10 volteos (estaba en la última tarjeta) |
| Promedio | alrededor de 5 volteos |
Ahora imagina 100 tarjetas. Promedio: alrededor de 50 volteos.
¿1,000 tarjetas? Promedio: alrededor de 500 volteos.
¿Ves el patrón? Dobla las tarjetas, dobla el trabajo. El trabajo crece en línea recta.
Los científicos informáticos llaman a esto búsqueda lineal — lineal significa que el trabajo crece como una línea: constante & predecible.
La búsqueda lineal funciona en CUALQUIER lista, ordenada o no. Eso la hace simple. Pero puede volverse lenta.
¿Cuántos Nombres?
Tienes una lista de clase de 20 nombres escritos en orden aleatorio.
Necesitas encontrar el nombre Zoe.
Verificas los nombres uno a la vez, de arriba hacia abajo en la lista.
Corta 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 búsqueda binaria.
Cómo funciona: abre en el nombre del medio (nombre #10). Pregunta: ¿está Zoe antes o después de este nombre?
Z viene cerca del final del alfabeto, por lo que Zoe viene DESPUÉS del medio. Descarta la primera mitad. Ahora solo te quedan los nombres 11-20.
Verifica el medio de esos 10 nombres (nombre #15). Z viene después de M, por lo que Zoe viene después del nombre #15. Descarta 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 Lista | Máx. Verificaciones con Búsqueda Binaria |
|---|---|
| 20 nombres | como máximo 5 verificaciones |
| 1,000 nombres | como máximo 10 verificaciones |
| 1,000,000 nombres | como máximo 20 verificaciones |
Compara eso con 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 — por eso se mantiene tan rápido.
Encuentra 'fig' en una Lista Ordenada
Aquí hay una lista ordenada de 8 palabras:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Quieres encontrar fig usando búsqueda binaria.
Recuerda: verifica el medio, pregunta si tu objetivo viene antes o después, luego corta la lista por la mitad.
Intercambiando Vecinos en Orden
Ordenamiento Burbuja: Compara Vecinos & Intercambia
El ordenamiento burbuja ordena una lista comparando dos elementos vecinos a la vez.
Si dos vecinos están desordenados — intercámbialos.
Sigue haciendo pasadas a través de la lista hasta que nada necesite ser intercambiado.
Ejemplo: ordena [5, 3, 8, 1]
Pasada 1:
- Compara 5 & 3. 5 > 3, por lo que intercambia → [3, 5, 8, 1]
- Compara 5 & 8. 5 < 8, no intercambies → [3, 5, 8, 1]
- Compara 8 & 1. 8 > 1, por lo que intercambia → [3, 5, 1, 8]
Pasada 2:
- Compara 3 & 5. OK → [3, 5, 1, 8]
- Compara 5 & 1. 5 > 1, intercambia → [3, 1, 5, 8]
- Compara 5 & 8. OK → [3, 1, 5, 8]
Pasada 3:
- Compara 3 & 1. 3 > 1, intercambia → [1, 3, 5, 8]
- Compara 3 & 5. OK. Compara 5 & 8. OK.
¡Listo! [1, 3, 5, 8] ✓
Observa: el número más grande burbujea hacia el final de la lista en cada pasada. Así es como el ordenamiento burbuja obtiene su nombre.
El ordenamiento burbuja funciona. No es el más rápido para listas grandes, pero es fácil de entender — perfecto para aprender.
Ordena [4, 2, 7, 1] con Ordenamiento Burbuja
Ordena esta lista usando ordenamiento burbuja: [4, 2, 7, 1]
Muestra la lista después de cada pasada. Cuenta cuántas pasadas toma terminar.