Búsqueda Binaria

Tengo la suerte de impartir clase a alumnos en Matemáticas II y también en TIC. Ha coincidido que hemos visto el Teorema de Bolzano en clase de matemáticas:

Sea f una función real continua en un intervalo cerrado [a,b] con f(a) y f(b) de signos contrarios. Entonces existe al menos un punto c del intervalo abierto (a, b) con f(c) = 0.

Que es tan simple como entender la siguiente gráfica:

La demostración no es tan sencilla, de hecho se utiliza resultados axiomáticos que podríamos no dar por verdaderos, pero elegimos que lo sean. Lema de Zorn, Axioma de elección, y equivalentes...como también damos por supuesto que toda sucesión monótona creciente y acotada es convergente, o que todo espacio vectorial tiene una base. Este teorema puede demostrarse en contextos bien diferentes dentro de las matemáticas (topológico, geometríco, analítico, algebráico), aunque realmente todos utilizan el mismo axioma que damos por verdadero.

Nosotros en clase, hemos visto el axioma de Cantor, o también llamado principio de los intervalos encajados, que es exactamente la misma idea que se utiliza en el algoritmo de la búsqueda binaria, aunque en un entorno finito. 

Por el momento, estamos empezando con algo de JS, como lenguaje formal de programación, pero ya podemos empezar a intentar algo menos formal, en Scratch, pero igual de interesante, ya que lo que buscamos es el desarrollo del pensamiento computacional.

MateAdivino

Un pseudocódigo del proyecto podría ser algo así:

1. Sea min=1 y max=1000
2. Si min>max entonces algo salió mal.
3. Sea Centro= punto medio de (min,max)
4. ¿Es Centro? ¡Lo encontraste! N= Centro
5. Si Centro < N entonces min=N+1
6. Si Centro > N entonces max=N-1
7. Regresa al paso 2

Si en cada iteración dividimos por la mitad, como mucho llegamos a 10 iteraciones, ya que 2^10= 1024, y nuestro intervalo tiene 1000 números, o mejor dicho el logaritmo en base 2 de 1000 es aproximadamente 9,966. Por eso hemos dibujado un círculo en ángulos de 36 grados, pues es el resultado de dividir el ángulo completo 360 grados entre 10.

TAREA: ¿Podrías mejorar el programa haciendo variable la cifra 1000?