Answer to the leet code question https://leetcode.com/problems/median-of-two-sorted-arrays/description/

median_of_two_sorted_arrays.cpp

class Solution {
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2);
    int find_at_index(size_t index, vector<int> &nums1, vector<int> &nums2);
};
using namespace std;

void print_range(std::vector<int>::iterator begin, std::vector<int>::iterator end){
    for(; begin < end; begin++){
        std::cout << *begin << ",";
    }
    std::cout << std::endl;
}

int Solution::find_at_index(size_t index, vector<int> &nums1, vector<int> &nums2) {
    if(index > nums1.size() + nums2.size()){
        cerr << "Index too large to search for\n";
        return 0;
    }
    //The maximum index to search for in any array is the index itself. So the lengths of
    //the arrays can be restricted
    auto length = index + 1;
    auto len1 = min(nums1.size(), length);
    auto len2 = min(nums2.size(), length);

    auto begin1 = nums1.begin();
    auto begin2 = nums2.begin();

    auto end1 = begin1 + len1;
    auto end2 = begin2 + len2;


    while(true){
        auto len1 = distance(begin1, end1);
        auto len2 = distance(begin2, end2);
        if(length > len1 + len2) {
            cerr << "length should be smaller than the lengths fo the two arrays\n";
            return 0;
        }

        //To simplify the code allways have the shorter array first
        if(len1 > len2) {
            swap(begin1, begin2);
            swap(end1, end2);
            swap(len1, len2);
        }

        if(len1 == 0) {
            return *(begin2 + len2 - 1);
        }

        if(length == 1) {
            return min(*begin1, *begin2);
        }

        auto half_length = length/2;

        //The smaller array might be shorter than half a length.
        //The remaining length can be used in the other array.
        auto small_length = len1 < half_length ? len1 : half_length;
        auto mid1 = begin1 + small_length - 1;
        auto mid2 = begin2 + (length - small_length) - 1;

        //Swap so that array 1 has the smaller mid
        if(*mid1 > *mid2){
            swap(begin1, begin2);
            swap(mid1, mid2);
            swap(end1, end2);
        }

        //We can ignore array 1's prefix as it is guaranteed
        //to have lower indexes than index
        length = length - distance(begin1, mid1 + 1);
        begin1 = mid1 + 1;
        end2 = mid2 + 1;
    }
}

double Solution::findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    auto length = nums1.size() + nums2.size();
    if(length % 2 == 0){
        auto index1 = (length - 1)/2;
        auto index2 = index1 + 1;
        auto value1 = this->find_at_index(index1, nums1, nums2);
        auto value2 = this->find_at_index(index2, nums1, nums2);
        return (value1 + value2)/2.0;
    } else {
        return this->find_at_index(length/2, nums1, nums2);
    }
}