884308. Median of 2 Sorted Arrays of Same Size
Hard
Median of 2 Sorted Arrays of Same Size
Slug: median-of-2-sorted-arrays-of-same-size
Difficulty: Hard
Id: 884308
Topic Tags: Binary Search, Arrays
Company Tags: Amazon, Microsoft, Samsung, Google
Summary
Given two sorted arrays of the same size, find the median of the combined array. The median is defined as the middle value in a sorted array when it has an odd length, and the average of the two middle values when it has an even length.
Detailed Explanation
To solve this problem, we can use binary search to efficiently find the median. Here's a step-by-step breakdown:
- First, combine the two arrays into one sorted array.
- Calculate the total length of the combined array.
- If the total length is odd, the median is the middle value. We can find this by using binary search to find the index where the median would be located.
- If the total length is even, the median is the average of the two middle values. We can again use binary search to find the indices of these two middle values.
Here's a diagram illustrating the process:
Array 1: [1, 3, 5]
Array 2: [2, 4, 6]
Combined array: [1, 2, 3, 4, 5, 6]
Total length: 6 (even)
Median = (3 + 4) / 2 = 3.5
Optimized Solutions
Java
public class Median {
public static double findMedian(int[] arr1, int[] arr2) {
int n = arr1.length;
int[] combined = new int[2 * n];
System.arraycopy(arr1, 0, combined, 0, n);
System.arraycopy(arr2, 0, combined, n, n);
Arrays.sort(combined);
int totalLength = combined.length;
if (totalLength % 2 == 1) {
return combined[totalLength / 2];
} else {
return (combined[totalLength / 2 - 1] + combined[totalLength / 2]) / 2.0;
}
}
}