Algoritmos y Estructuras de Datos (VJ1215)

Este algoritmo devuelve el número secreto; suponemos que disponemos de una función intentar que nos dice si el número secreto es mayor o menor en cada intento (podría consistir en preguntarle al usuario).

int adivinarNumero() {

   // En una primera fase va multiplicando por 2 hasta encontrar
   // el número secreto o superarlo, empezando en 1

   int numero = 1;
   string respuesta = intentar(numero);

   while (respuesta == "es mayor") {
      numero = numero * 2;
      respuesta = intentar(numero);
   }

   if (respuesta != "es menor")
      return numero;

   // Si no lo ha encontrado, en una segunda fase realiza
   // una búsqueda binaria entre los dos últimos numeros

   int limiteInferior = numero / 2 + 1;
   int limiteSuperior = numero - 1;

   while (limiteInferior < limiteSuperior) {
      numero = (limiteInferior + limiteSuperior) / 2;
      respuesta = intentar(numero);
      if (respuesta == "es mayor")
	 limiteInferior = numero + 1;
      else if (respuesta == "es menor")
	 limiteSuperior = numero - 1;
      else
	 return numero;
   }

   return limiteInferior;

}
      

Por ejemplo, supongamos que el número secreto es 23. En la primera fase, los intentos son 1, 2, 4, 8, 16 y 32. En la segunda fase, los intentos son 24, 20, 22 y 23.

Código de prueba y versión interactiva