Guess the number with a twist

Question

I wrote a program where the computer guesses a random number.

To do this, I implemented a form of binary search. This correctly handles any edge-cases that I know of, including 0 and std::numeric_limits<int>::max(). This doesn't handle negative numbers (since rand will never return one) but that could easily be fixed.

The average amount of tries it takes to guess the number is around 29 or 30.

Here it is:

#include <functional>
#include <iostream>
#include <cstdlib>
#include <limits>
#include <ctime>

static int random_number;

int compare(int guess)
{
    if(guess > random_number)
        return 1;
    if(guess < random_number)
        return -1;
    return 0;
}

struct guess_stats
{
    int guesses = 0;
    int number = 0;
};

guess_stats finder(std::function<int(int)> &&cmp)
{
    int max = std::numeric_limits<int>::max();
    int min = 0;
    int guess = (min + max) / 2;
    int cmp_result;
    guess_stats results;

    do
    {
        cmp_result = cmp(guess);

        if(cmp_result < 0)
        {
            std::cout << "Greater than " << guess;
            min = guess;
            const int diff = max - guess;
            guess += diff - (diff / 2);
        }
        else if(cmp_result > 0)
        {
            std::cout << "Less than " << guess;
            max = guess;
            const int diff = guess - min;
            guess -= diff - (diff / 2);
        }

        std::cout << '\n';

        results.guesses++;
    } while(cmp_result);

    results.number = guess;

    return results;
}

int main(void)
{
    std::srand(std::time(0));
    random_number = std::rand();
    guess_stats stats = finder(compare);

    std::cout << "Number: " << stats.number << '\n'
              << "Guesses: " << stats.guesses << '\n';

    return 0;
}

What I'm looking for:

• Although I don't expect there will be, are there any edge-cases I may not have seen?
• Are there any algorithmic changes that I could make to have less time-complexity? I don't think so (because this is only O(log n) as it is), but I may be surprised to find out.
• Are there any better ways to generate random numbers? I used srand, time, and rand in this program, but those are old solutions. I imagine C++ has something much more up-to-date for generation of random numbers.
• Any other general advice on what to improve would be appreciated.

Answer 1

Non-const static variables

Your code shows a lot of good practices:

• variables are always initialized when possible
• variables have proper names (and you stuck to a single naming scheme)
• no unecessary std::endl

However, there is one drawback:

static int random_number;

That line right there is, at least from my point of view, a flaw. static variables are a nice escape hatch in some circumstances, but here it's unnecessary. We can easily use another argument to finder, for example:

guess_stats finder(comparison_function && cmp, int random_number) {
   ...
}

Or we could combine the comparison function with the number to be guessed in a struct, similar to guess_stats.

Either variant makes sure that our changes in finder won't spill into the rest of our program flow. While we don't intend to change random_number in finder, it's easy to accidentally write random_number++ or press <Tab> in an IDE with the wrong completion. If we were to use multiple finder variants in separate threads, we would have a hard time to debug the behaviour, especially if there is more than a single static variable.

However, I guess you've used random_number as a static variable to ease the use of compare. There are other ways that we will inspect at the end of this review.

Note that const static or constexpr static variables on the other hand are fine, as they cannot lead to debugging troubles (unless you const_cast them, but at that point we're deep within undefined behaviour territory).

Q&A

Although I don't expect there will be, are there any edge-cases I may not have seen?

What happens if I use the following comparison?

int compare(int unused) {
    return 1;
}

Sure, that's not a valid comparison, however, there is nothing in finder that blocks us from using such a function. Given that a binary search should take at most \$\log_2(n)+1\$ steps, we can introduce a simple limit of 33 iterations.

Are there any algorithmic changes that I could make to have less time-complexity? I don't think so (because this is only O(log n) as it is), but I may be surprised to find out.

That's all correct, and from an \$\mathcal O\$ analysis there's nothing to improve.

Are there any better ways to generate random numbers?

There's the <random> header. We can use the example code from uniform_int_distribution to generate a random number:

int main(void)
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dist(0, std::numeric_limits<int>::max());

    const int random_number = dist(gen);

    ...
}

However, keep in mind that this usually won't seed a mt19937 correctly and there are ways around that issue.

Getting rid of random_number

Given that we use <functional>, we use at least C++11. Therefore, we have lambdas at hand. We can use this to our advantage to get rid of random_number in main:

int main(void)
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dist(0, std::numeric_limits<int>::max());

    const int random_number = dist(gen);

    auto compare = [random_number](int guess) {
        if (guess > random_number) {
            return 1;
        } else if (guess < random_number) {
            return -1;
        }
        return 0;  
    };

    guess_stats stats = finder(compare);
    ...
}

We don't even need to change finder to use the new comparison, thanks to std::function<int(int)>&&.