Hola.
La búsqueda binaria, o también llamada dicotómica, es muy sencilla de realizar.
La mecánica es la misma que el típico juego de tener que adivinar un numero y que las únicas pistas que te dan al decir un número, es si el número que tienes que acertar es mayor o menor.
Si yo te pido que adivines un número entre un determinado rango, en el menor número de intentos posibles, pues si tú eres medianamente listo, no te vas a poner a decir números al azar, si no que me preguntarás siempre por el número central, es decir, por la mitad de ese rango.
Pues, aunque no aciertes en ese intento, pregutnar por el número que está en el centro te va a permitir descartar la mitad del total de números.
Ejemplo:
- Yo te digo que adivines un número entre el 1 y el 100.
- Tú me dirás, ¿el 50?
- Yo te digo: No, es mayor.
Bien, no has acertado, pero ahora ya sabes que puedes descartar todos los números entre el 1 y el 50. El numero a encontrar estará entre el 51 y el 100.
Con una sola pregunta, ya has descartado la mitad de números. Pues ahora, sigues la misma estrategia:
-Tu dices, ¿el 75? (75 es más o menos el número central del rango entre 51 y 100)
- Yo te digo: No, es menor
Guay, sigues sin acertar, pero ya sabes que puedes decartar los número entre el 75 y el 100.
Con solo dos preguntas, has reducido el rango a números entre 51 y 74.
LA estrategia es buena, has de seguir preguntando por el valor central de ese rango, pues ya hemos visto que esto permite descartar el mayor número posible de valores en caso de no acertar.
Sin embargo, ahora no es tan obvio cuál es el valor central entre 51 y 74. Nuestra generación no es muy buena con el cálculo mental je je...
pero bueno, tú ahora sacarías el teléfono móvil y te ayudarías de la calculadora para obtener el valor central de ese rango.
Si el rango es 51 a 74, pues calculo cuantos números hay en total dentro de ese rango: 74 - 51 = 23
Hay 23 numeros en total, la mitad de este total es 23 / 2 = 11
Pues ese 11 se lo sumo a 51 y así obtengo el valor central de este rango. 51 + 11 = 66
Preguntar por el 66 es la mejor opción para poder descartar el mayor número de valores en caso de no acertar.
- Tu me dices: el 66
- Yo digo: No, es mayor
OK, el rango ahora va del 67 al 74. Con solo tres preguntas hemos conseguido reducir tanto las posibilidades que ya casi no quedan números.
Venga, calculemos el valor central con la misma formula de antes:
74 - 67 = 7 ¡¡Ya solo quedan 7 posibilidades!!, de entre las 100 que habían antes de tus tres intentos.
7 / 2 = 3
67 + 3 = 70
Tú dices: ¿el 70?
Yo digo: No, es menor (probablemente estaría mintiendo intentando no darte ya la victoria, pero bueno..)
Pues nada, tu sigues aplicando tu busqueda binaria:
¿Menor que 70? Pues ahora el rango se reduce a valores entre 67 y 69, incluidos.. ¡¡Ya solo quedan tres posibilidades!!; 67, 68 y 69
Aquí no hace falta usar la calculadora para adivinar el valor centra, es evidente que es el 68.
Pero vamos a fingir que somos tan estúpidos como un ordenador, y vamos a aplicar la fórmula igualmente, pues es lo que hará el programa en Java que realice esta búsqueda:
69 - 67 = 2
2 / 2 = 1
67 + 1 = 68
- Tu dices: ¿el 68?
- Yo prolongo la mentira hasta las últimas consecuencias y digo: No..emmm.., ¡¡es mayor!!
¿Mayor? Pues vale. Esto significa que el rango se queda reducido a valores entre 69 y 69.., es decir, solo hay una posibilidad, el 69.
Pero de nuevo fingimos ser ordenador estúpido, que jamás será capaz de obtener un dato si no es gracias a una fórmula matemática.
Así que venga, le damos a la calculadora por última vez, para obtener el "valor central" del rango que va del 69 al 69 xD
69 - 69 = 0
0 / 2 = 0
69 + 0 = 69
- Tú dices: Es el 69, pues no quedan más números y lo he acertado en apenas 6 intentos.
- Yo, digo: ¡¡Correcto!! y no me queda más remedio que felicititarte.
Bien, toda esta bonita historia que he contado sobre aquella vez que jugamos tú y yo a acertar un numero entre el 1 y el 100, es para darnos cuenta de dos cosas:
1º El gran potencial de la búsqueda binaria o dicotómica. Con un máximo de 6 intentos, se puede acertar un número de entre 100 posibilidades.
Y esta capacidad de encontrar un número con pocos intentos es exponencial. Luego pondré un código Java que es capaz de acertar un número entre 50000000 con apenas unos 25/26 intentos.
2º Quería que vieras cuál es la mecánica a seguir. Quería que vieras que es lo que le tenemos que decir al programa para que sepa realizar la búsqueda binaria.
Ha de saber averiguar cuál es el valor central del rango de valores posibles.
Y según si el número a adivinar es mayor o menor, ha de saber crear un nuevo rango con los valores que NO SE HAN DESCARTADO y, de nuevo, calcular el valor central de este nuevo rango.
Por eso he insistido en repetir los pasos matemáticos, incluso cuando ya solo quedaba una única posibilidad, pues eso es lo que hará el programa.
Yo todo esto lo hago valiéndome de tres variables tipo int.
Las que llamo rangoMinimo y rangoMaximo son las que definen el menor y mayor valor posible respectivamente.
OBiviamente, al comenzar el programa, rangoMinimo apuntará a la posicion 0 del array y rangoMaximo a la última posicion del array.
Es decir:
La que llamo mitad, es la que calcula el "valor central" del rango y esa será la posición del array que consultaremos a ver si coincide con el número a buscar.
Cada intento fallido, reducirá el rango.
Si el numero que buscamos es mayor que el que está en "mitad", habrá que modificar el rangoMínimo:
Si mitad era 50, y nos dicen que el número es mayor, pues ahora el valor mínimo posible es 51 (mitad + 1)
Los numeros entre 0 y 50 quedan descartados.
En cambio si es menor, modificamos rangoMaximo:
Si mitad era 50 y el número es menor, pues ahora el valor máximo posibles es 49 (mitad - 1).
Los número entre 51 y 100 quedan descartados.
Con el nuevo rango ya calculado, basta con que aplicar la formula que explicabamos antes para calcular el "valor central" y guardarlo en la variable mitad:
Esto es lo mismo que hacíamos en la "historia" de ejemplo:
69 - 67 = 2
2 / 2 = 1
67 + 1 = 68
Todo se hace dentro de un bucle, que se irá repitiendo hasta que acertemos el número (con un booleano podemos decirle al bucle si lo hemos acertado o no) o si ya no quedan más números por los que preguntar, es decir, cuando el rangoMínimo sea mayor que el rangoMaximo.
Ojo, no cuando sean iguales, porque esto significa que aún queda un valor posible por el que preguntar.
Pero si este tampoco es, ya que a lo mejor hemos decidido crear un array con números al azar y a lo mejor no contiene el número que el usuario quiere buscar, entonces llegaría un momento en que el rango minimo sería mayor que el rango maximo. Y esto significa que ya no quedan posiciones en el array por los que seguir preguntando.
En fin, creo que ya he escrito demasiado. EL programa no es complejo, pero requiere unas cuantas explicaciones para comprender su lógica.
Ya te he relatado los pasos a seguir. Si intentas hacerlo tú por tu cuenta, aunque no lo consigas, mejor para tí.
Si no, o bien te quedas atascado o lo que sea, aquí te dejo mi código para que lo consultes cuando quieras.
En el genero un array de 50000000 números al azar. Ya verás que al ordenador le toma unos pocos segundos rellenarlo y luego ordenarlo de menor a mayor.
Un saludo.
