interpolation_search.h

#ifndef INTERPOLATION_SEARCH_H
#define INTERPOLATION_SEARCH_H
 
#ifdef __cplusplus
#include <algorithm>
#include <cstdint>
#include <vector>
#endif

template <typename Iterator, typename T>
int64_t interpolation_search(Iterator begin, Iterator end, T key) {
    auto size = std::distance(begin, end);
 
    auto it_begin = begin;
    auto it_end = end - 1;
 
    while (size > 0 && *it_begin <= key && *it_end >= key) {
        auto guess = it_begin;
        if (*it_end != *it_begin) {
            auto offset = static_cast<int>(static_cast<double>(size - 1) * (key - *it_begin) /
                                           (*it_end - *it_begin));
            std::advance(guess, offset);
        }
        if (*guess == key) {
            return std::distance(begin, guess);
        }
 
        if (*guess > key) {
            it_end = guess - 1;
        } else {
            it_begin = guess + 1;
        }
        size = std::distance(it_begin, it_end) + 1;
    }
 
    return static_cast<int64_t>(-1);
}
 
#endif // INTERPOLATION_SEARCH_H