guess.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>

//! Administers a number-guessing game.
class GuessingGame {
public:
  enum hint_type { TOO_HIGH = -1, CORRECT = 0, TOO_LOW = 1 };

  //! Start a new guessing game with a random number n where lo <= n <= hi.
  GuessingGame (int lo, int hi)
    : myNumber(rand() / (RAND_MAX / (hi - lo + 1)) + lo) {
  }

  //! Checks a guess against the current number.
  //! @param   n   the guess
  //! @return      TOO_LOW, TOO_HIGH, or CORRECT
  hint_type guess (int n) const {
    if (n < myNumber) return TOO_LOW;
    if (n > myNumber) return TOO_HIGH;
    return CORRECT;
  };

private:
  int myNumber;
};

// Given that a number is contained in a certain range, guess the number
// in the middle of that range (thus dividing the range into two halves,
// "numbers lower than the guess" and "numbers higher than the guess").
// If that is the target, stop. Otherwise, find out which half of the range
// contains the target and try again with that half as the new range.
namespace guess {
  /**
   * Recursive binary search algorithm to guess a number in a range.
   *
   * @param   g      an instance of the guessing game
   * @param   low    low bound
   * @param   high   high bound
   * @return         the target number
   **/
  int recursive (GuessingGame &g, int low, int high) {
    int myguess = (low + high) / 2;

    switch (g.guess(myguess)) {
    case GuessingGame::TOO_HIGH: return recursive(g, low,         myguess);
    case GuessingGame::TOO_LOW:  return recursive(g, myguess + 1, high);
    default:                     return myguess;
    }
  }

  /**
   * Iterative binary search algorithm to guess a number in a range.
   *
   * @param   g      an instance of the guessing game
   * @param   low    low bound (lowest possible number)
   * @param   high   high bound (the highest possible number plus one)
   * @return         the target number
   **/
  int iterative (GuessingGame &g, int low, int high) {
    while (true) {
      int myguess = (low + high) / 2;

      switch (g.guess(myguess)) {
      case GuessingGame::TOO_HIGH: high = myguess;     break;
      case GuessingGame::TOO_LOW:  low  = myguess + 1; break;
      default:                     return myguess;
      }
    }
  }
}

int main () {
  std::srand(std::time(0));
  int low = 0, high = 100;
  GuessingGame g(low, high);
  int n = guess::iterative(g, low, high);
  std::cout << "The number is " << n << std::endl;
}