ternary_search.h

#ifndef TERNARY_SEARCH_H
#define TERNARY_SEARCH_H
 
#ifdef __cplusplus
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
#endif
 
namespace {
template <typename Iter, typename T> Iter ternary_search(Iter first, Iter last, T value) {
    while (first < last) {
        typedef typename std::iterator_traits<Iter>::difference_type diff_t;
        diff_t diff = std::distance(first, last) / 3;
        Iter mid1 = first + diff;
        Iter mid2 = mid1 + diff;
 
        if (*mid1 == value)
            return mid1; // Found value
        else if (*mid2 == value)
            return mid2; // Found value
 
        if (value < *mid1)
            last = mid1;
        else if (value > *mid2)
            first = mid2 + 1;
        else {
            first = mid1 + 1;
            last = mid2;
        }
    }
    return last; // Not found
}
} // namespace
template <typename Container, typename T> int64_t ternary_search(Container& c, const T& value) {
    auto it = ternary_search(c.begin(), c.end(), value);
    if (it != c.end() && *it == value)
        return static_cast<int64_t>(std::distance(c.begin(), it));
    else
        return -1;
}
 
#endif // TERNARY_SEARCH_H