Exponential search

I recently discovered the exponential search algorithm which can be used to find whether a value exists in an ordered range. An exponential search checks whether a value is smaller than the \$2^n\$th element of the range, then if the searched value is indeed smaller, it performs a binary search in the range \$[2^n, 2^{n-1})\$ to check whether the value exists in this range, otherwise it starts again by comparing the value to the \$2^{n+1}\$th element, etc... Here is my implementation of the algorithm for random-access iterators (I could make it work with forward iterators too but it has a cost):

#include 
#include 
#include 

template
>
auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool
{
    using difference_type = typename std::iterator_traits::difference_type;

    difference_type size = std::distance(first, last);
    if (first == last) return false;

    difference_type bound = 1;
    while (bound < size && not compare(key, first[bound]))
    {
        bound *= 2;
    }

    auto end = first + std::min(bound, size);
    return std::binary_search(first + bound / 2, end, key, compare);
}

However, while implementing this algorithm, I remembered a nice property of binary search, which is notably exploited by the Ford-Johnson merge-insertion sort: searching a value in \$2^n\$ elements and in \$2^{n+1}-1\$ takes the same number of comparisons (e.g. binary search in collections of size \$16\$ and \$31\$ requires the same number of comparisons). Therefore I modified the algorithm so that it would always search in sequences whose size is \$2^n-1\$ to maximize its efficiency:

```
#include
#include
#include

template
>
auto exponential_search(Iterator first, Iterator last,
const T& key, Compare compare={})
-> bool
{
using difference_type = typename std::iterator_traits::difference_type;

difference_type size = std::distance(first, last);
if (firs

Just a few miscellaneous comments about a few points:

template
>

Rather than just Iterator, I'd rather see it given a name reflecting the (minimum) category of iterator expected. In this case, it looks like it probably only really makes sense for a random-access iterator, but I'm not entirely certain of that.

auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool

I realize some people like to use trailing return types (in general), but I'd prefer to see them reserved for times they're really needed. In a case like this, it just adds syntactic noise.

using difference_type = typename std::iterator_traits::difference_type;

difference_type size = std::distance(first, last);
if (first == last) return false;

Given that you've just computed the size, it's probably at least worth considering whether to use that result, and just use:

if (size == 0) return false;

...instead of pretty much re-computing the same thing via first == last.

Below you use first[bound] and in general, the algorithm seems to really require random access iterators to make much sense. If so, I'd rather just use last - first instead of std::distance to compute the difference.

StackExchange Code Review Q#119665, answer score: 4