Guess the number with a twist
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 &amp;&amp; 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 &lt;Tab&gt; 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&amp;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 &lt;random&gt; 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&lt;int&gt; dist(0, std::numeric_limits&lt;int&gt;::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 &lt;functional&gt;, 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&lt;int&gt; dist(0, std::numeric_limits&lt;int&gt;::max());

    const int random_number = dist(gen);

    auto compare = [random_number](int guess) {
        if (guess &gt; random_number) {
            return 1;
        } else if (guess &lt; 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&lt;int(int)&gt;&amp;&amp;.