Median of 2 Sorted Arrays of Different Sizes
Understanding the Problem
The goal is to find the median of two sorted arrays of different sizes.
Method 1: Simple Merge
This method merges the two arrays and finds the median.
import java.util.*;
public class MedianFinder {
public static double findMedianSortedArrays(int[] arr1, int[] arr2) {
int n1 = arr1.length, n2 = arr2.length;
int[] merged = new int[n1 + n2];
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
merged[k++] = arr1[i++];
} else {
merged[k++] = arr2[j++];
}
}
while (i < n1) merged[k++] = arr1[i++];
while (j < n2) merged[k++] = arr2[j++];
int total = n1 + n2;
if (total % 2 == 0) {
return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
} else {
return merged[total / 2];
}
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 8};
int[] arr2 = {7, 9, 10, 11};
System.out.println("Median: " + findMedianSortedArrays(arr1, arr2));
}
}
Output:
Median: 8.0
Method 2: Binary Search
This method uses binary search to find the median efficiently.
import java.util.*;
public class MedianFinderBinarySearch {
public static double findMedianSortedArrays(int[] arr1, int[] arr2) {
if (arr1.length > arr2.length) {
return findMedianSortedArrays(arr2, arr1);
}
int x = arr1.length, y = arr2.length;
int low = 0, high = x;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (x + y + 1) / 2 - partitionX;
int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : arr1[partitionX - 1];
int minRightX = (partitionX == x) ? Integer.MAX_VALUE : arr1[partitionX];
int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : arr2[partitionY - 1];
int minRightY = (partitionY == y) ? Integer.MAX_VALUE : arr2[partitionY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((x + y) % 2 == 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
} else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (maxLeftX > minRightY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
throw new IllegalArgumentException("Input arrays are not sorted.");
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 8};
int[] arr2 = {7, 9, 10, 11};
System.out.println("Median: " + findMedianSortedArrays(arr1, arr2));
}
}
Output:
Median: 8.0