Comparison between exhaustive search, binary search, and linear fit / interpolation search for sorted arrays.

search.cpp

#include <chrono>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <random>
#include <cassert>

// Comparison between exhaustive search, binary search, and linear fit / interpolation search for sorted arrays.

typedef std::vector<float>::iterator iterator;

int exhaustive(const std::vector<float>& vec, const float value)
{
    int vsize = vec.size();
    for(int i = 0; i < vsize; ++i) 
        if(vec[i] > value) 
            return i;

    return -1;
}

iterator exhaustive(iterator first, iterator last, const float value)
{
    for(; first != last; ++first) 
        if(*first > value) 
            return first;

    return last;
}

int binary(const std::vector<float>& vec, const float value)
{
    int p = 0, q = vec.size();
    int m;
    while(p < q)
    {
        m = (p + q) / 2;
        if(vec[m] < value)
           p = m + 1;
        else
           q = m;
    }
    return p;
}

iterator binary(iterator first, iterator last, const float value)
{
    iterator mid;
    while(first < last)
    {
        mid = first + (last - first) / 2;
        if(*mid < value)
           first = mid + 1;
        else
           last = mid;
    }
    return first;
}

// cf : https://blog.demofox.org/2019/03/22/linear-fit-search/
int linear_fit_search(const std::vector<float>& vec, const float value)
{
    int p = 0, q = vec.size() - 1, g;
    float vmin = vec.front(), vmax = vec.back();
    while( p < q )
    {
        g = p + int((value - vmin) * (q - p) / (vmax - vmin));

        if( vec[g] < value )
        {
            vmin = vec[g];
            p = g+1;
        }
        else
        {
            vmax = vec[g];
            q = g;
        }
    }
    return p;
}

// cf : https://blog.demofox.org/2019/03/22/linear-fit-search/
iterator linear_fit_search(iterator first, iterator last, const float value) 
{
    iterator mid;
    --last;
    float vmin = *first, vmax = *last;
    while( first < last )  
    {
        mid = first + (value - vmin) * (last - first) / (vmax - vmin);
        if( *mid < value )    
        {
            first = mid + 1;
            vmin = *mid;
        } 
        else    
        {
            last = mid;
            vmax = *mid;
        }
    }
    return first;
}

static std::vector<float> generate_data(size_t size)
{
    using value_type = float;

    static std::uniform_real_distribution<value_type> distribution(0.f, 1.f);
    static std::random_device rnd;
    static std::mt19937 engine(rnd());

    std::vector<value_type> data(size);
    std::generate(data.begin(), data.end(), []() { return distribution(engine); });
    return data;
}

struct Timer
{
    typedef std::chrono::high_resolution_clock clock;
    typedef std::chrono::duration<int, std::nano> nanoseconds;
    typedef std::chrono::duration<int, std::micro> microseconds;
    typedef std::chrono::duration<int, std::milli> milliseconds;
    typedef std::chrono::duration<int, std::ratio<1>> seconds;
    typedef std::chrono::duration<int, std::ratio<60>> minutes;

    explicit Timer(bool run = true) {if (run) reset();}

    void reset() {start = clock::now();}

    nanoseconds nano() const {return std::chrono::duration_cast<nanoseconds>(clock::now() - start);}
    microseconds micro() const {return std::chrono::duration_cast<microseconds>(clock::now() - start);}
    seconds sec() const {return std::chrono::duration_cast<seconds>(clock::now() - start);}

    template <typename T, typename Traits>
    friend std::basic_ostream<T, Traits>& operator<<(std::basic_ostream<T, Traits>& out, const Timer& timer)
    {
        return out << timer.nano().count() << " ns";
    }

    clock::time_point start;
};

int main( int argc, char * argv[] )
{
    std::vector<float> data = generate_data(1000000);
    std::sort(data.begin(), data.end());

    float value = 0.724356548f;
    // float value = 0.000024356548f;
    
    Timer timer;
    int a = exhaustive(data, value);
    // std::cout << "exhaustive index " << timer << std::endl;

    timer.reset();
    a = exhaustive(data, value);
    std::cout << "exhaustive index " << timer << std::endl;

    timer.reset();
    auto ita = exhaustive(data.begin(), data.end(), value);
    std::cout << "exhaustive iterator " << timer << std::endl;

    timer.reset();
    int b = binary(data, value);
    std::cout << "binary index " << timer << std::endl;
    assert( value >= data[b-1] && value <= data[b] );

    timer.reset();
    auto itb = binary(data.begin(), data.end(), value);
    std::cout << "binary iterator " << timer << std::endl;
    assert( value >= *(itb-1) && value <= *itb );
    
    timer.reset();
    int c = linear_fit_search(data, value);
    std::cout << "linear fit index " << timer << std::endl;

    timer.reset();
    iterator itc = linear_fit_search(data.begin(), data.end(), value);
    std::cout << "linear fit iterator " << timer << std::endl;

    assert( a == b );
    assert( a == c );
    assert( a == (int)(std::distance(data.begin(), ita)));
    assert( a == (int)(std::distance(data.begin(), itb)));
    assert( a == (int)std::distance(data.begin(), itc) );

    return 0;
}