4

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int xLen = nums1.size(), yLen = nums2.size();
        int low=0, high=xLen;
        double ans;

        // Corner case when yLen is 0.
        if(yLen == 0){
            int mid = xLen/2;
            if(xLen&1)
                return double(nums1[mid]);
            else
                return double(nums1[mid]+nums1[mid-1])/2.0;
        }

        while(low <= high){
            int partitionX = (low+high)/2;
            int partitionY = (xLen+yLen+1)/2 - partitionX;

            // Handle case where partitionY goes out of bound.
            if(partitionY < 0){
                high = partitionX-1;
                continue;
            }
            if(partitionY > yLen){
                low = partitionX+1;
                continue;
            }

            // Find max element of left sides.
            int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX-1];
            int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY-1];

            // Find min elements of right sides.
            int minRightX = (partitionX == xLen) ? INT_MAX : nums1[partitionX];
            int minRightY = (partitionY == yLen) ? INT_MAX : nums2[partitionY];

            // If conditon is satisfied.
            if(maxLeftX <= minRightY && maxLeftY <= minRightX){
                if((xLen+yLen)&1)
                    ans = max(maxLeftX, maxLeftY);
                else
                    ans = double((max(maxLeftX, maxLeftY)+min(minRightX, minRightY))/2.0);
                break;
            }
            else if(maxLeftX > minRightY){ // Move to left.
                high = partitionX-1;
            }
            else{  // Move to right.
                low = partitionX+1;
            }
        }
        return ans;
    }
};