Bug Report for median-of-two-sorted-arrays, faulty solution for C++ provided

[Dino-Zunic]

Faulty solution for C++ "Median of Two Sorted Arrays"

There is error in solution 4. Binary Search (Optimal) code snipped, which looks like this:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int>& A = nums1;
        vector<int>& B = nums2;
        int total = A.size() + B.size();
        int half = (total + 1) / 2;

        if (B.size() < A.size()) {
            swap(A, B);
        }
        // the rest of the code is not shown...
    }
};

The line swap(A, B) is only supposed to make reference A refer to B, and vice versa. However, these aren't pointers but references. Since references cannot be changed after initialization, this line ends up swapping the contents of the two vectors instead. This is not the intended behavior, and it increases time complexity from O(min(n, m)) to O(max(n, m)).

This can be fixed by using pointers instead of references, or by doing the following:

class Solution {
public:

    double findMedianSmallerFirst(const vector<int> &A, const vector<int> &B) const {
        int total = A.size() + B.size();
        int half = (total + 1) / 2;
        int l = 0;
        int r = A.size();
        while (l <= r) {
            int i = (l + r) / 2;
            int j = half - i;

            int Aleft = i > 0 ? A[i - 1] : INT_MIN;
            int Aright = i < A.size() ? A[i] : INT_MAX;
            int Bleft = j > 0 ? B[j - 1] : INT_MIN;
            int Bright = j < B.size() ? B[j] : INT_MAX;

            if (Aleft <= Bright && Bleft <= Aright) {
                if (total % 2 != 0) {
                    return max(Aleft, Bleft);
                }
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
            } else if (Aleft > Bright) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return -1;
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        return nums1.size() <= nums2.size() ? 
                        findMedianSmallerFirst(nums1, nums2) :
                        findMedianSmallerFirst(nums2, nums1);
    }
};