Exponential search

Question

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 <algorithm>
#include <functional>
#include <iterator>

template<
    typename Iterator,
    typename T,
    typename Compare = std::less<>
>
auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool
{
    using difference_type = typename std::iterator_traits<Iterator>::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 <algorithm>
#include <functional>
#include <iterator>

template<
    typename Iterator,
    typename T,
    typename Compare = std::less<>
>
auto exponential_search(Iterator first, Iterator last,
                        const T& key, Compare compare={})
    -> bool
{
    using difference_type = typename std::iterator_traits<Iterator>::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]))
    {
        first += bound;
        size -= bound;
        bound = std::min((bound + 1) * 2 - 1, size);
    }

    return std::binary_search(first, first + bound, key, compare);
}

My tests show that it always performs at worst as many comparisons as the original version, and often fewer when looking for the same element in the same sequence (except when looking for the second element of the collection for some reason).

I know that the algorithm could be more efficient when equivalent values appear in the collection, but I didn't find any elegant way to solve this, even though three-way comparators could have been a nice solution.

Is there any way I can improve this algorithm, be it from a style, correctness or efficiency point of view?

Answer 1

Just a few miscellaneous comments about a few points:

template<
    typename Iterator,
    typename T,
    typename Compare = std::less<>
>

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<Iterator>::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.

Answer 2

I agree with most of the remarks by @JerryCoffin. In addition, I would shorten the computation of size and bound to a single initialization using auto:

{
    if (first == last) return false;

    auto size = std::distance(first, last), bound = 1;
    // as before
}

This will enforce that size and bound have the same type, and you'd probably don't really care what type that is (it's not used in your interface anyway).

If you really like the iterator traits, then I'd suggest writing an auxiliary helper trait:

template<class It>
using difference_t = typename std::iterator_traits<It>::difference_type;