Find median of two sorted ranges Given two sorted ranges of elements, compute a median of all the elements in O(log(n+m)) time.

This solution contains only one call to std::lower_bound 

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

template &lt;typename It1, typename It2&gt;
auto max_end(It1 begin1, It1 end1, It2 begin2, It2 end2) {
    if (begin1 != end1 &amp;&amp; begin2 != end2) {
        return std::max(*std::prev(end1), *std::prev(end2));
    }
    if (begin1 != end1) {
        return *std::prev(end1);
    }
    if (begin2 != end2) {
        return *std::prev(end2);
    }
    // both ranges should never be empty
    __builtin_unreachable();
}

template &lt;typename It1, typename It2&gt;
auto min_begin(It1 begin1, It1 end1, It2 begin2, It2 end2) {
    if (begin1 != end1 &amp;&amp; begin2 != end2) {
        return std::min(*begin1, *begin2);
    }
    if (begin1 != end1) {
        return *begin1;
    }
    if (begin2 != end2) {
        return *begin2;
    }
    // both ranges should never be empty
    __builtin_unreachable();
}


template&lt;typename RandomAccessIterator1, typename RandomAccessIterator2&gt;
auto median2(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
              RandomAccessIterator2 begin2, RandomAccessIterator2 end2) {
    static_assert(std::is_same&lt;typename std::iterator_traits&lt;RandomAccessIterator1&gt;::value_type,
                  typename std::iterator_traits&lt;RandomAccessIterator2&gt;::value_type&gt;::value,
                  "Value types of two ranges must be the same");
    ssize_t n1 = std::distance(begin1, end1);
    ssize_t n2 = std::distance(begin2, end2);
    ssize_t mid = (n1 + n2) / 2;
    auto it = std::lower_bound(begin1, end1, 42, [&amp;](const auto &amp; item, int){
        ssize_t i1 = &amp;item - &amp;*begin1;
        ssize_t i2 = mid - i1;
        // make sure i2 is a valid index
        if (i2 &lt; 0) {return false;}
        if (i2 &gt; n2) {return true;}

        return max_end(begin1, begin1+i1, begin2, begin2+i2)
                &gt;= min_begin(begin1+i1, end1, begin2+i2, end2);
    });

    ssize_t i1 = &amp;*it - &amp;*begin1;
    ssize_t i2 = mid - i1;

    if ((n1 + n2) % 2) {
        return min_begin(begin1+i1, end1, begin2+i2, end2);
    }

    return (max_end(begin1, begin1+i1, begin2, begin2+i2) +
            min_begin(begin1+i1, end1, begin2+i2, end2)) / 2;
}

template&lt;typename Rng1, typename Rng2&gt;
auto median2(Rng1 &amp;&amp;rng1, Rng2 &amp;&amp;rng2) {
    using std::begin;
    using std::end;
    return median2(begin(rng1), end(rng1), begin(rng2), end(rng2));
}

int main() {
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 2, 3, 4}, std::vector&lt;float&gt;{}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{}, std::vector&lt;float&gt;{1, 2, 3, 4}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 2, 3, 4, 5}, std::vector&lt;float&gt;{}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{}, std::vector&lt;float&gt;{1, 2, 3, 4, 5}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 2}, std::vector&lt;float&gt;{3}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 3}, std::vector&lt;float&gt;{2}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 2, 3, 4, 5}, std::vector&lt;float&gt;{6, 7, 8, 9, 10}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 2, 3, 4, 5}, std::vector&lt;float&gt;{6, 7, 8, 9}) &lt;&lt; '\n';
    std::cout &lt;&lt; median2(std::vector&lt;float&gt;{1, 2, 3}, std::vector&lt;float&gt;{6, 7, 8, 9}) &lt;&lt; '\n';
}


Live on Coliru

Solution to the same problem in Python on codereview
While this is not a thorough code review, here are some things you could improve or should pay attention to:


median2 is dangerous for containers which offer RandomAccessIterators, but aren't contiguous. In particular, ssize_t i1 = &amp;item - &amp;*begin1; invokes undefined behavior if item and begin1 do not belong to the same memory area, which they might if the underlying container is not contiguous (also, sometimes operator&amp; is overwritten, which can cause a lot of problems on its own). To prepare against this, I would advise you to rename RandomAccessIterator[12] to ContiguousRandomAccessIterator[12] or something in that line of wording.
You are probably aware of this already, but your code is not really portable. For one, there is __builtin_unreachable, which is a gcc builtin. Also, ssize_t is a type from unistd.h, which is a posix header and might not be available on non-posix-conformant operating systems (also, you do currently not include this header, which is a bug). ssize_t is easily replaceable by std::ptrdiff_t in most cases, but if you care for that much of correctness, you could also write something like using difference_t = typename std::iterator_traits&lt;RandomAccessIterator1&gt;::difference_type; and use that instead. For __builtin_unreachable(), if the optimization value you get by using it is really that important for you, you should wrap it in some compiler identifying macro. If it is not important (which is probably the case), you could do a variety of things, for example replace it with a throw expression or just return a default value. 
Rng[12] is a very confusing template parameter name, at least to me. I would expect it to stand for "random number generator", which is not fitting here. Choosing a different name would likely be beneficial here.
You should consider passing std::pairs instead of separate iterators. This makes clear that one begin- and one end-iterator always belong together, and helps cleaning up the parameters of your functions.
std::vector&lt;float&gt;{1, 2, 3, 4}. Please don't. This code is just ugly. The reason is that 1) you are relying on implicit conversion for all your values (why not write std::vector&lt;float&gt;{1.0f, 2.0f, 3.0f, 4.0f} instead?) and 2) there is no reason here to use float at all. Stick to integer types unless you do something that actually requires floating point features.