Encontrar lo que quieres rápido
Cuando buscas una palabra en un diccionario, no pasas hoja por hoja desde la primera. Abres por el medio y decides "¿adelante o atrás?" Si está en orden, puedes cortar a la mitad cada vez y encontrarlo mucho más rápido.
Uno por uno, desde el inicio
La forma más simple de buscar
es mirar desde el inicio, uno por uno.
"¿Este? No.
¿El siguiente? No."
Sigues pasando
hasta que coincide.
Es seguro, pero
si está cerca del final,
toma un rato.
Uno por uno desde el frente. (Objetivo 13 · revisa una casilla a la vez)
Con pocas casillas,
está bien.
¿Pero con miles?
Yendo uno por uno
toma una eternidad.
Hay una forma mejor.
Una forma astuta que usas
cuando las cosas están en orden.
Abre por el medio
Cuando está en orden,
haz esto.
Abre el medio y mira.
Si tu objetivo es mayor,
tira la mitad de adelante.
Si es menor, la de atrás.
Cada vez que miras,
desaparece la mitad.
Mira el medio, tira la mitad. (Objetivo 13 · descarta la mitad donde no está)
Tirando la mitad cada vez,
lo que queda encoge rápido.
8 casillas a 4,
4 a 2,
2 a 1.
En unos pocos pasos
se reduce a una casilla.
Uno por uno vs por mitades
Pon los dos lado a lado
y busca el mismo valor.
Uno por uno
tiene que mirar muchas veces
un valor cerca del final.
Por mitades
termina en unos pocos.
La misma respuesta,
pero los pasos difieren mucho.
Busca el mismo valor (13), compara pasos. (Uno por uno = lento · por mitades = rápido)
Cuantas más casillas,
mayor la diferencia.
Mil uno por uno
es hasta mil miradas,
por mitades unas diez.
Esta diferencia, con datos grandes,
es enorme.
Por qué ordenar va primero
Cortar a la mitad
tiene una condición.
Debe estar en orden.
Solo estando ordenado
se cumple "si es mayor que el medio, tira lo de adelante."
Si está revuelto,
no puedes tirar una mitad.
Cortar a la mitad funciona solo si está ordenado. (En orden → funciona · revuelto → no)
Así que ordenar y buscar
son compañeros.
Ordénalo una vez,
y desde entonces buscar
sigue siendo más rápido.
El esfuerzo de ordenar
se recompensa una y otra vez.
Mira hasta dónde llegamos
Buscar siempre está cerca.
Un diccionario, una guía telefónica,
una palabra escrita en un buscador.
Detrás de ella,
una forma como "cortar a la mitad"
encuentra la respuesta rápido.
Orden, ordenar, buscar
ahora se conectan en una línea.
Orden → ordenar → buscar, hasta aquí. (Buscar = sacar lo que quieres, rápido)
Un algoritmo
no es nada grandioso,
ya lo ves.
Poner un orden,
ordenar,
buscar con astucia.
Pequeñas mañas reunidas
hacen grandes cosas.