#include <iostream>

#include <vector>
#include <iterator>

using namespace std;

template<typename t_iter>
t_iter binarySearch(t_iter begin, t_iter end, typename iterator_traits<t_iter>::value_type q)
{
    typedef iterator_traits<t_iter>::value_type t_elem;
    size_t len = end - begin;

    if (len < 2)
    {
        if (*begin == q)
        {
            return begin;
        }

        return end;
    }

    t_iter middleElem = begin + len / 2;

    if (*middleElem < q)
    {
        return binarySearch(middleElem, end, q);
    }

    return binarySearch(begin, middleElem, q);
}

int main()
{
    int tmp[] = {1, 2, 4, 5, 8, 10, 20, 35, 41, 42, 100};
    size_t len = sizeof(tmp)/sizeof(tmp[0]);
    vector<int> a(tmp, tmp + len);

    int q = 35;

    auto it = binarySearch(a.begin(), a.end(), q);

    cout << distance(a.begin(), it) << endl;
}

template<typename t_iter>
t_iter binarySearch(t_iter begin, t_iter end, typename iterator_traits<t_iter>::value_type q)
{
    auto len = std::distance(begin, end);

    while(len>1)
    {
        t_iter middleElem = begin;
        std::advance(middleElem, len / 2);

        if (*middleElem < q)
        {
            begin = middleElem;
        }
        else
        {
            end = middleElem;
        }
        len = std::distance(begin, end);
    }

    if (*begin == q)
    {
        return begin;
    }
    return end;

}

if (len < 2)
{
    if (*begin == q)

typedef iterator_traits<t_iter>::value_type t_elem;

auto it = binarySearch(a.begin(), a.end(), q);

int tmp[] = {1, 2, 4, 5, 8, 10, 20, 35, 41, 42, 100};
size_t len = sizeof(tmp)/sizeof(tmp[0]);
vector<int> a(tmp, tmp + len);

vector<int> a = {1, 2, 4, 5, 8, 10, 20, 35, 41, 42, 100};

typedef typename iterator_traits<t_iter>::value_type t_elem;

using t_elem = typename iterator_traits<t_iter>::value_type;

template <class Iterator>
using Value_type = typename std::iterator_traits<Iterator>::value_type;

template<typename t_iter>
t_iter binarySearch(t_iter begin, t_iter end, Value_type<t_iter> q)

t_iter middleElem = begin + len / 2;