To find the median of two sorted arrays nums1 and nums2, you can follow a binary search approach that combines both arrays to find the partition points that divide the combined arrays into two halves of approximately equal length. Here’s a step-by-step guide on how to do it
- Ensure
nums1is the smaller array (if not, swap them) to optimize the partitioning process. - Use binary search on the smaller array (
nums1) to find a partition indexpartition1such that the elements to the left ofpartition1are smaller than or equal to the elements on the right. - Calculate the corresponding partition index
partition2in the larger array (nums2) using the formulapartition2 = (m + n + 1) / 2 - partition1. - Calculate the four boundary values:
maxLeft1,maxLeft2,minRight1, andminRight2. These represent the elements around the partition points.maxLeft1=nums1[partition1 - 1]ifpartition1 > 0, otherwise negative infinitymaxLeft2=nums2[partition2 - 1]ifpartition2 > 0, otherwise negative infinityminRight1=nums1[partition1]ifpartition1 < m, otherwise positive infinityminRight2=nums2[partition2]ifpartition2 < n, otherwise positive infinity
- Check if the combined length of the two arrays (
m + n) is even or odd. If even, the median is(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2. If odd, the median ismax(maxLeft1, maxLeft2).
Median of Two Sorted Arrays using Python
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
low, high = 0, m
while low <= high:
partition1 = (low + high) // 2
partition2 = (m + n + 1) // 2 - partition1
maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
minRight1 = float('inf') if partition1 == m else nums1[partition1]
minRight2 = float('inf') if partition2 == n else nums2[partition2]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
if (m + n) % 2 == 0:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
else:
return max(maxLeft1, maxLeft2)
elif maxLeft1 > minRight2:
high = partition1 - 1
else:
low = partition1 + 1
raise ValueError("Input arrays are not sorted!")
Median of Two Sorted Arrays using C#
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.Length > nums2.Length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.Length;
int n = nums2.Length;
int low = 0;
int high = m;
while (low <= high) {
int partition1 = (low + high) / 2;
int partition2 = (m + n + 1) / 2 - partition1;
int maxLeft1 = (partition1 == 0) ? int.MinValue : nums1[partition1 - 1];
int maxLeft2 = (partition2 == 0) ? int.MinValue : nums2[partition2 - 1];
int minRight1 = (partition1 == m) ? int.MaxValue : nums1[partition1];
int minRight2 = (partition2 == n) ? int.MaxValue : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
} else {
return Math.Max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
high = partition1 - 1;
} else {
low = partition1 + 1;
}
}
throw new ArgumentException("Input arrays are not sorted!");
}
Median of Two Sorted Arrays using Java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int low = 0;
int high = m;
while (low <= high) {
int partition1 = (low + high) / 2;
int partition2 = (m + n + 1) / 2 - partition1;
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
high = partition1 - 1;
} else {
low = partition1 + 1;
}
}
throw new IllegalArgumentException("Input arrays are not sorted!");
}
Median of Two Sorted Arrays using Java Script
var findMedianSortedArrays = function(nums1, nums2) {
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1]; // Swap arrays if needed
}
const m = nums1.length;
const n = nums2.length;
let low = 0;
let high = m;
while (low <= high) {
const partition1 = Math.floor((low + high) / 2);
const partition2 = Math.floor((m + n + 1) / 2) - partition1;
const maxLeft1 = (partition1 === 0) ? -Infinity : nums1[partition1 - 1];
const maxLeft2 = (partition2 === 0) ? -Infinity : nums2[partition2 - 1];
const minRight1 = (partition1 === m) ? Infinity : nums1[partition1];
const minRight2 = (partition2 === n) ? Infinity : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 === 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
high = partition1 - 1;
} else {
low = partition1 + 1;
}
}
throw new Error("Input arrays are not sorted!");
};