In this program, we are going to share a simple merge based O(n) solution to find median of two sorted arrays. If you are a Java beginner and want to start learning the Java programming, then keep your close attention in this tutorial as I am going to share how to write a simple Merge based O(n) solution to find median of two sorted arrays.
Copy the below Java program and execute it with the help of Javac compiler. At the end of this program, We have shared the output of this program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
class Main { // function to calculate median static int getMedian(int ar1[], int ar2[], int n) { int i = 0; int j = 0; int count; int m1 = -1, m2 = -1; /* Since there are 2n elements, median will be average of elements at index n-1 and n in the array obtained after merging ar1 and ar2 */ for (count = 0; count <= n; count++) { /* Below is to handle case where all elements of ar1[] are smaller than smallest(or first) element of ar2[] */ if (i == n) { m1 = m2; m2 = ar2[0]; break; } /* Below is to handle case where all elements of ar2[] are smaller than smallest(or first) element of ar1[] */ else if (j == n) { m1 = m2; m2 = ar1[0]; break; } if (ar1[i] < ar2[j]) { /* Store the prev median */ m1 = m2; m2 = ar1[i]; i++; } else { /* Store the prev median */ m1 = m2; m2 = ar2[j]; j++; } } return (m1 + m2)/2; } /* Driver program to test above function */ public static void main (String[] args) { int ar1[] = {1, 12, 15, 26, 38}; int ar2[] = {2, 13, 17, 30, 45}; int n1 = ar1.length; int n2 = ar2.length; if (n1 == n2) System.out.println("Median is " + getMedian(ar1, ar2, n1)); else System.out.println("arrays are of unequal size"); } } |
Median is 16
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
