¿A que no adivinas que número estoy pensando?

Foto de MetalPhoeniX bajo una licencia Creative Commons

Mi novia y yo estábamos jugando con los sobrinos a adivinar que número estaba pensando la otra persona. Para los que no hayan jugado nunca se trata de que A diga un número y si no acierta B le dice si el número pensado es mayor o menor.

Jugábamos con números del 1 al 10 o si queríamos que la partida se alargase del 1 al 100, en este último caso acababan usando un montón de intentos (incluso repetían números que no se acordaban que habían dicho). En eso que les aseguré que era capaz de adivinar cualquier número del 1 al 10.000 en 20 intentos máximo. La primera vez lo hice en 12 cosa que atribuyeron a la suerte, la segunda en 14 (creo)... jajaja, bueno los niños son un publico fácil, al menos en esto.

El método no es muy difícil, es ir reduciendo el número de candidatos a la mitad cada vez. Por ejemplo
-5.000
-menos
-2.500
-menos
-1.250
-mas
(etc)

Lo que no es tan inmediato es saber cuantos intentos se necesitan de antemano como máximo. Para calcular el numero de intentos se hace el logaritmo base 2 del número de candidatos. De esta manera el número de intentos necesarios en nuestro caso es log₂10.000 = 13,29 intentos. Para hacerlo de cabeza contáis el número de ceros (4 en nuestro caso) y lo multiplicáis por 3, os quedará un número aproximado a la baja. Por ejemplo si el rango es de 1 a 1.000.000 es aprox 6x3=18 (en realidad 20).

Todo esto se utiliza bastante en programación en búsquedas en listas ordenadas. En realidad la mayoría de nosotros lo ha hecho, porque de las miles de personas que aparecen en la guía telefónica apenas tardamos 1 minuto en dar con el que buscamos, o con las miles de entradas que tiene un diccionario. Pensemos como lo hacemos, buscamos la palabra "pereza" abrimos el diccionario por un poco más de la mitad, nos aparece "muerte" como "muerte" va antes que pereza nos olvidamos de todas las palabras que hay antes de muerte (acabamos de reducir la búsqueda a la mitad), ahora buscamos en la mitad de las páginas que nos quedan, aparece "pardo" (uy, ya casi estamos) etc. Si nos fijamos lo que hacemos es ir acotando la búsqueda, no haciendo una exhaustiva.

Pero sólo lo podemos hacer con listas ordenadas. Si el diccionario no siguiese ningún orden preestablecido (o no lo conociésemos nosotros), estaríamos obligados a hacer una búsqueda exhaustiva, es decir, ir mirando una por una todas las palabras. ¿Como se busca en un diccionario chino? jejeje