#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <ctime>

int main(void)
{
  int max = 10000000;
  std::srand(static_cast<unsigned>(std::time(0)));
//  std::random_device rnd; // random_device not working properly under Windows MinGW
  std::vector<std::uint32_t> v(10);
//  std::generate(v.begin(), v.end(), std::ref(rnd));
  std::generate(std::begin(v), std::end(v), std::rand);
  auto seed = std::seed_seq(std::begin(v), std::end(v));
  auto rand = std::bind(std::uniform_int_distribution<>(1, max - 1), std::mt19937(seed));
  int ans = rand();
  int iter = 0, tmp = 0, dis = 0;
  std::string str = "", gt = "greater than ans", lt = "less than ans";

  while (true) {
    iter++;
    if (iter == 1) {
      tmp = max / 2;
      dis = tmp / 2;
      str = (tmp > ans) ? gt : lt;
    } else if (tmp > ans) {
      tmp -= dis;
      if (dis > 1)
        dis /= 2;
        str = gt;
      } else if (tmp < ans) {
        tmp += dis;
        if (dis > 1)
          dis /= 2;
        str = lt;
      }
      if (tmp == ans)
        str = "hit!";
      std::cout << "iter = " << iter << ", tmp = " << tmp << " " << str << std::endl;
      if (tmp == ans)
        break;
  }
}