Búsqueda binaria
Busca el 23 en la lista ordenada [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] con búsqueda binaria. Después responde: en una lista ordenada de 1.000.000 de cédulas, ¿cuántas comparaciones necesita en el peor caso?
Cómo se resuelve
- 1La búsqueda binaria exige que la lista esté ordenada. Mira el elemento del medio y, según sea mayor o menor que lo buscado, descarta la mitad entera de un solo golpe.
- 2Posiciones 0 a 9. Arrancamos con izq = 0 y der = 9. El medio es (0 + 9) ÷ 2 = 4 (división entera), y ahí está el 16. Como 16 < 23, lo buscado está a la derecha: izq pasa a 5.
- 3Ahora izq = 5 y der = 9. El medio es (5 + 9) ÷ 2 = 7, y ahí está el 56. Como 56 > 23, está a la izquierda: der pasa a 6.
- 4Ahora izq = 5 y der = 6. El medio es (5 + 6) ÷ 2 = 5, y ahí está el 23. Encontrado en la posición 5, con 3 comparaciones.
- 5Para el caso general: cada comparación parte la lista a la mitad, así que el número de pasos es cuántas veces se puede dividir 1.000.000 entre 2 hasta llegar a 1, es decir log₂(1.000.000).
- 62¹⁹ = 524.288 y 2²⁰ = 1.048.576, así que log₂(1.000.000) está entre 19 y 20: con 20 comparaciones alcanza.
Respuesta: El 23 está en la posición 5 y se encuentra en 3 comparaciones. En 1.000.000 de cédulas bastan 20 comparaciones en el peor caso, frente a 1.000.000 de la búsqueda lineal.
El error de siempre: Aplicarla sobre una lista que no está ordenada. No da error ni avisa: simplemente responde «no está» para un elemento que sí estaba, y el fallo aparece semanas después. El otro clásico es escribir el bucle con while izq < der en vez de izq <= der: cuando queda un solo elemento nunca se compara, y se pierden justo los valores que caen en ese borde.
Quicksort
Aplica una pasada de partición de Quicksort sobre [7, 2, 9, 4, 1, 8] tomando como pivote el último elemento, el 8. ¿Cómo queda la lista y dónde queda el pivote?
Cómo se resuelve
- 1Partir no es ordenar. El objetivo de una pasada es solo dejar el pivote en su posición definitiva, con todos los menores o iguales a su izquierda y todos los mayores a su derecha.
- 2Pivote = 8. Se lleva una frontera que marca dónde termina la zona de los «menores o iguales»; al empezar, esa zona está vacía.
- 3Se recorre de izquierda a derecha comparando con 8. El 7 es ≤ 8: la frontera avanza a la posición 0 y el 7 ya está ahí, no se mueve nada. El 2 es ≤ 8: la frontera avanza a la 1 y el 2 tampoco se mueve.
- 4El 9 es > 8: no se hace nada y la frontera se queda en la posición 1. Este es el paso que crea el desorden aparente.
- 5El 4 es ≤ 8: la frontera avanza a la posición 2 y el 4 se intercambia con lo que hay ahí, que es el 9. La lista queda [7, 2, 4, 9, 1, 8].
- 6El 1 es ≤ 8: la frontera avanza a la posición 3 y el 1 se intercambia con el 9. Queda [7, 2, 4, 1, 9, 8].
- 7Terminado el recorrido, el pivote se intercambia con el primer elemento mayor que él, el de la posición 4. Queda [7, 2, 4, 1, 8, 9].
Respuesta: La lista queda [7, 2, 4, 1, 8, 9]. El 8 queda en la posición 4, ya en su lugar definitivo, y Quicksort sigue ordenando por separado [7, 2, 4, 1] y [9].
El error de siempre: Esperar que después de la partición la mitad izquierda quede ordenada. No lo está, [7, 2, 4, 1] sigue revuelta, y no tiene por qué estarlo: lo único garantizado es que todos son ≤ 8. El otro error, más caro, es tomar siempre el último elemento como pivote sin mirar los datos: si la lista ya venía ordenada, cada partición deja un lado vacío y Quicksort degenera a O(n²) justo en el caso que uno creería más fácil.
