Given two sorted arrays of integers, we want to find the Median of the elements of the two sorted array.
Example: A = { 2, 4, 10, 11, 12, 14 } and B = { 1, 5 }
Output: 7.5. Since (5 + 10 )/2 = 7.5
Solution:
The trick here is how to merge them together.
Steps
- We create a new empty array, C, with the size of A+B
- we iterate through A and B simultaneously with two variables i and j and check if A[i] < B[j] and save which ever is smaller in to C.
- At this point we run out the number in the shorter array, if any. So we need to copy the rest of the elements from the longest array to the result array C.
Once the two sorted arrays are merged in to one single sorted array C, then calculating the median is as easy as picking the middle element if the number of items in C is odd or calculate the average of the middle two elements.
public double FindMedianSortedArrays(int[] a, int[] b) {
int[] c = MergeArrays(a, b);
double median = 0;
int n = c.Length;
if (n % 2 == 0) {
median = (c[(n / 2) - 1] + c[(n / 2)]) / 2.0;
}
else {
median = c[(n / 2)];
}
return median;
}
public static int[] MergeArrays(int [] a, int [] b) {
int[] c = new int[a.Length + b.Length];
int i = 0,j = 0, k=0;
while ( i<a.Length && j < b.Length) {
if(a[i] < b[j]) {
c[k] = a[i];
i++;k++;
}
else {
c[k] = b[j];
j++;k++;
}
}
while (i < a.Length) {
c[k] = a[i];
i++;k++;
}
while(j < b.Length) {
c[k] = b[j];
j++;k++;
}
return c;
}