median_of_two_sorted_arrays.cc

// https://leetcode.com/problems/median-of-two-sorted-arrays

// https://www.youtube.com/watch?v=LPFhl65R7ww
// https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation

class Solution {
public:
    double findMedianSortedArrays(vector<int>& a1, vector<int>& a2) {
        if (a1.size() > a2.size()) swap(a1, a2); // ensure a1 is shorter

        int n1 = a1.size(), n2 = a2.size(), lo = 0, hi = n1;

        while (lo <= hi) {
            int cut1 = lo + (hi - lo)/2;
            int cut2 = n1 + (n2 - n1)/2 - cut1;

            // if cut1 = 0 then there is nothing on left side: denote it with INT_MIN
            int l1 = cut1 == 0  ? INT_MIN : a1[cut1 - 1];
            int r1 = cut1 == n1 ? INT_MAX : a1[cut1];

            // if cut2 = 0 then there is nothing on right side: denote it with INT_MAX
            int l2 = cut2 == 0  ? INT_MIN : a2[cut2 - 1];
            int r2 = cut2 == n2 ? INT_MAX : a2[cut2];

            // cut1 is too far on the right side, go left
            if (l1 > r2) hi = cut1 - 1;
            // else, it is too far on the left side, go right
            else if (l2 > r1) lo = cut1 + 1;
            // correct cut: manage case where n1 + n2 is even/odd
            else return (n1 + n2) % 2 ? min(r1, r2) : (max(l1, l2) + min(r1, r2))/2.;
        }

        return -1; // case where a1 and a2 are unsorted
    }
};