Cómo funciona la búsqueda en algoritmos

De uno en uno desde el principio

La forma más sencilla de buscar es mirar cada elemento desde el principio.
"¿Es este? No. ¿El siguiente? No." Sigues hasta encontrarlo.
Es seguro, pero si el valor está cerca del final, tarda mucho.

Pulsa "buscar de uno en uno" para revisar una casilla cada vez desde el principio. El valor buscado es 13.

Con pocas casillas, no pasa nada.
Pero con miles o decenas de miles, revisar de una en una lleva muchísimo.
Hay una forma mejor, una muy lista que se puede usar cuando las cosas están en orden.

Abrir por la mitad

Cuando las cosas están en orden, se hace así: primero abres por la mitad y miras.
Si el valor que buscas es mayor, descartas la mitad de delante; si es menor, descartas la de detrás.
Cada mirada elimina la mitad.

Cada vez que pulsas "mirar la mitad", se descarta entera la mitad donde no puede estar el valor. El valor buscado es 13.

Al descartar la mitad cada vez, lo que queda se reduce muy deprisa.
8 casillas pasan a 4, 4 pasan a 2 y 2 pasan a 1.
Con unas pocas miradas, llegas a una sola casilla.

De uno en uno vs a mitades

Pon las dos formas lado a lado y busca el mismo valor.
Buscar de uno en uno exige mirar muchas veces para llegar a un valor cercano al final, mientras que partir a mitades termina en unas pocas miradas.
Misma respuesta, número de pasos muy distinto.

Buscando el mismo valor (13), compara los pasos. De uno en uno = lento · a mitades = rápido.

Cuantas más casillas, mayor es la diferencia.
Con mil elementos, de uno en uno puede llevar hasta mil miradas, mientras que a mitades bastan unas diez.
Con muchos datos, esa diferencia es enorme.

Por qué primero hay que ordenar

Partir a mitades tiene una condición: las cosas deben estar en orden.
Solo si están ordenadas se cumple que "si es mayor que la mitad, puedes descartar la parte de delante".
Si están revueltas, no se puede descartar la mitad.

Partir a mitades solo funciona si está ordenado. En orden → se cumple · revuelto → no se cumple.

Por eso ordenar y buscar van de la mano.
Una vez que has puesto las cosas en fila, buscar sigue siendo rápido desde entonces.
El esfuerzo de ordenar se recompensa una y otra vez.

Hasta dónde hemos llegado

Buscar está siempre a nuestro alrededor.
Diccionarios, guías telefónicas, la palabra que escribes en un buscador: detrás, métodos como partir a mitades encuentran la respuesta rápido.
El orden, la ordenación y la búsqueda ya están unidos en una sola línea.

Orden → ordenación → búsqueda: hasta aquí hemos llegado. Buscar = sacar rápido lo que quieres.

A estas alturas ya ves que los algoritmos no tienen nada de grandioso.
Fijar un orden, ordenar las cosas y buscar con ingenio.
Pequeños trucos que, juntos, consiguen grandes resultados.