Median of Two Sorted Arrays

Median

It is middle element when n is odd and
average of middle two elements when n is even.

PartitionX = 2 means there are 2 elements on the left side,

partitionX = 2 means there are 2 elements on the left side,

partitionY = 4 means there are 4 elements on the left side.

To calculate partitionY , we use (x+y+1)/2 to let it work with both odd and even length.

Using (x+y)/2 = pX+pY is wrong:
x = 5; y = 6; pX = 2; 
pX + pY = (x + y)/2 = 5; ==> pY= 5-2 = 3  Odd length is Wrong!!!! L x:2 + y:3 = 5(wrong); R x:3 + y:3 = 6
Why: We want pick MaxLeft(x,y) to be the median, here we want pick the 6th element as maxLeft(x,y), in the above case, 
the left side only have 5 elements, don't have the 6th one.

x = 4; y = 6; pX = 2;
pX + pY = (x+y)/2 = 5;  ==> 5-2=3   Even length is correct.

Using (x+y+1)/2 = pX+pY is correct for both odd and even length!
x = 5; y = 6; pX = 2; 
pX + pY = (x + y + 1)/2 = 6; ==> pY= 5-2 = 4  Odd length is also correct. L x:2 + y:4 = 6; R x:3 + y:2 = 5

x = 4; y = 6; pX = 2;
pX + pY = (x+y+1)/2 = 5;  ==> 5-2=3

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        //if input1 length is greater than switch them so that input1 is smaller than input2.
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int x = nums1.size();
        int y = nums2.size();

        int low = 0;
        int high = x;  // high is x (nums2.length), not x - 1;
        while (low <= high) {
            int partitionX = (low + high)/2;
            int partitionY = (x + y + 1)/2 - partitionX;

            //if partitionX is 0 it means nothing is there on left side. Use -INF for maxLeftX
            //if partitionX is length of input then there is nothing on right side. Use +INF for minRightX
            int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? INT_MAX : nums1[partitionX];

            int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? INT_MAX : nums2[partitionY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                //We have partitioned array at correct place
                // Now get max of left elements and min of right elements to get the median in case of even length combined array size
                // or get max of left for odd length combined array size.
                if ((x + y) % 2 == 0) {
                    return ((double)max(maxLeftX, maxLeftY) + min(minRightX, minRightY))/2;
                } else {
                    return (double)max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) { //we are too far on right side for partitionX. Go on left side.
                high = partitionX - 1;
            } else { //we are too far on left side for partitionX. Go on right side.
                low = partitionX + 1;
            }
        }
    }
};

1