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 <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
template <typename It1, typename It2>
auto max_end(It1 begin1, It1 end1, It2 begin2, It2 end2) {
if (begin1 != end1 && 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 <typename It1, typename It2>
auto min_begin(It1 begin1, It1 end1, It2 begin2, It2 end2) {
if (begin1 != end1 && 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<typename RandomAccessIterator1, typename RandomAccessIterator2>
auto median2(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
RandomAccessIterator2 begin2, RandomAccessIterator2 end2) {
static_assert(std::is_same<typename std::iterator_traits<RandomAccessIterator1>::value_type,
typename std::iterator_traits<RandomAccessIterator2>::value_type>::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, [&](const auto & item, int){
ssize_t i1 = &item - &*begin1;
ssize_t i2 = mid - i1;
// make sure i2 is a valid index
if (i2 < 0) {return false;}
if (i2 > n2) {return true;}
return max_end(begin1, begin1+i1, begin2, begin2+i2)
>= min_begin(begin1+i1, end1, begin2+i2, end2);
});
ssize_t i1 = &*it - &*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<typename Rng1, typename Rng2>
auto median2(Rng1 &&rng1, Rng2 &&rng2) {
using std::begin;
using std::end;
return median2(begin(rng1), end(rng1), begin(rng2), end(rng2));
}
int main() {
std::cout << median2(std::vector<float>{1, 2, 3, 4}, std::vector<float>{}) << '\n';
std::cout << median2(std::vector<float>{}, std::vector<float>{1, 2, 3, 4}) << '\n';
std::cout << median2(std::vector<float>{1, 2, 3, 4, 5}, std::vector<float>{}) << '\n';
std::cout << median2(std::vector<float>{}, std::vector<float>{1, 2, 3, 4, 5}) << '\n';
std::cout << median2(std::vector<float>{1, 2}, std::vector<float>{3}) << '\n';
std::cout << median2(std::vector<float>{1, 3}, std::vector<float>{2}) << '\n';
std::cout << median2(std::vector<float>{1, 2, 3, 4, 5}, std::vector<float>{6, 7, 8, 9, 10}) << '\n';
std::cout << median2(std::vector<float>{1, 2, 3, 4, 5}, std::vector<float>{6, 7, 8, 9}) << '\n';
std::cout << median2(std::vector<float>{1, 2, 3}, std::vector<float>{6, 7, 8, 9}) << '\n';
}