#define UNIT r2_bsearch
#include <vector>

using intvec = std::vector< int >;

int bsearch_idx( const intvec &vec, int val )
{
    auto b = vec.begin(), e = vec.end();

    while ( b < e ) /* the search interval is not empty */
    {
        auto mid = b + ( e - b ) / 2;
        if ( val < *mid ) e = mid;     /* must be in [b, mid) */
        if ( val > *mid ) b = mid + 1; /* must be in (mid, e) */
        if ( val == *mid )
            return std::distance( vec.begin(), mid ); /* we found it */
    }

    return vec.size();
}

auto bsearch( const intvec &vec, int val )
{
    return std::next( vec.begin(), bsearch_idx( vec, val ) );
}

auto bsearch( intvec &vec, int val )
{
    return std::next( vec.begin(), bsearch_idx( vec, val ) );
}

#include "test_main.cpp"