## Median of Two Sorted Arrays

• Time:O(\log\min(m, n))
• Space:O(1)

## C++

``````class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int n1 = nums1.size();
const int n2 = nums2.size();
if (n1 > n2)
return findMedianSortedArrays(nums2, nums1);

int l = 0;
int r = n1;

while (l <= r) {
const int partition1 = (l + r) / 2;
const int partition2 = (n1 + n2 + 1) / 2 - partition1;
const int maxLeft1 = partition1 == 0 ? INT_MIN : nums1[partition1 - 1];
const int maxLeft2 = partition2 == 0 ? INT_MIN : nums2[partition2 - 1];
const int minRight1 = partition1 == n1 ? INT_MAX : nums1[partition1];
const int minRight2 = partition2 == n2 ? INT_MAX : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
return (n1 + n2) % 2 == 0
? (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5
: max(maxLeft1, maxLeft2);
else if (maxLeft1 > minRight2)
r = partition1 - 1;
else
l = partition1 + 1;
}

throw;
}
};
``````

## JAVA

``````class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
final int n1 = nums1.length;
final int n2 = nums2.length;
if (n1 > n2)
return findMedianSortedArrays(nums2, nums1);

int l = 0;
int r = n1;

while (l <= r) {
final int partition1 = (l + r) / 2;
final int partition2 = (n1 + n2 + 1) / 2 - partition1;
final int maxLeft1 = partition1 == 0 ? Integer.MIN_VALUE : nums1[partition1 - 1];
final int maxLeft2 = partition2 == 0 ? Integer.MIN_VALUE : nums2[partition2 - 1];
final int minRight1 = partition1 == n1 ? Integer.MAX_VALUE : nums1[partition1];
final int minRight2 = partition2 == n2 ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1)
return (n1 + n2) % 2 == 0
? (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) * 0.5
: Math.max(maxLeft1, maxLeft2);
else if (maxLeft1 > minRight2)
r = partition1 - 1;
else
l = partition1 + 1;
}

throw new IllegalArgumentException();
}
}
``````

## Python

``````class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1 = len(nums1)
n2 = len(nums2)
if n1 > n2:
return self.findMedianSortedArrays(nums2, nums1)

l = 0
r = n1

while l <= r:
partition1 = (l + r) // 2
partition2 = (n1 + n2 + 1) // 2 - partition1
maxLeft1 = -2**31 if partition1 == 0 else nums1[partition1 - 1]
maxLeft2 = -2**31 if partition2 == 0 else nums2[partition2 - 1]
minRight1 = 2**31 - 1 if partition1 == n1 else nums1[partition1]
minRight2 = 2**31 - 1 if partition2 == n2 else nums2[partition2]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) * 0.5 if (n1 + n2) % 2 == 0 else max(maxLeft1, maxLeft2)
elif maxLeft1 > minRight2:
r = partition1 - 1
else:
l = partition1 + 1
``````