Binary search as a generic algorithm I am upgrading my C++11 knowledge and repeating some essential algorithm. Here is binary search only in terms of iterators.

#include &lt;iostream&gt;

#include &lt;vector&gt;
#include &lt;iterator&gt;

using namespace std;

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

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

        return end;
    }

    t_iter middleElem = begin + len / 2;

    if (*middleElem &lt; 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&lt;int&gt; a(tmp, tmp + len);

    int q = 35;

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

    cout &lt;&lt; distance(a.begin(), it) &lt;&lt; endl;
}
Iterators may not be random access iterators which means the length calculation and the advance by half won't compile.

For this there is the distance and advance functions available which use the random access if it is available but fall back to counting and repeated incrementing when it isn't.

You never use the t_elem type def.

In the recursion step both branches are equally likely and equally important, that is best signified and made more readable by using an else branch rather than letting it fall through.

you can also implement as a loop to minimize recursion overhead (micro-optimization admittedly because automatic tail-call optimization would do the same).

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

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

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

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

}