4 Median of Two Sorted Arrays

Solution
So happy that I come up with my own version of solution, yeah! With clean thought and a (somewhat) bug-proof implementation!

class Solution {
public:
    int findKth(vector<int>&nums1, vector<int>& nums2, int i1, int i2, int k) {
        int n1 = nums1.size(), n2 = nums2.size();
        if ( i1 == n1 ) return nums2[i2+k-1];
        if ( i2 == n2 ) return nums1[i1+k-1];
        if ( k == 1 ) return min(nums1[i1], nums2[i2]);

        // determine how many to jump in nums1 and nums2:
        int delta1 = k/2;
        if ( i1 + delta1-1 >= n1 ) delta1 = n1 - i1;
        int delta2 = k - delta1;
        if ( i2 + delta2-1 >= n2 ) {
            delta2 = n2-i2;
            delta1 = k - delta1;
        }
        if ( nums1[i1+delta1-1] < nums2[i2+delta2-1] ) return findKth(nums1, nums2, i1+delta1, i2, k-delta1);
        else return findKth(nums1, nums2, i1, i2+delta2, k-delta2);
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if ( (n1+n2)%2 == 1 ) return findKth(nums1, nums2, 0, 0, (n1+n2+1)/2);
        double med1 = findKth(nums1, nums2, 0, 0, (n1+n2)/2);
        double med2 = findKth(nums1, nums2, 0, 0, (n1+n2)/2+1);
        return (med1+med2)/2;
    }
};

Notes

• The $$O(N)$$ solution is super easy. But it can be made $$O(logN)$$ via binary search technique.
• Instead of comparing numbers one by one, we use a "jumping" technique.
  • Say, if we are now starting with nums1[i1] and nums2[i2], and want to find the $$k_{th}$$ element. We jump to nums1[i1+x-1] and nums2[i1 + (k-x) -1], making the comparison.
  • The smaller one can never be the k-th largest. For example, if nums1[i1+x-1] < nums2[i2+(k-x)-1], the pointer for nums1 can directly move to the next position (nums[i1+x]) and search for the $$(k-x)_{th}$$ element recursively.
  • Note the termination of the recursion.
  • But be very careful with the possibility that the index goes out of the array.