Hactoberfest2021/Median_of_2_SortedArrays.java at main · python4geeks/Hactoberfest2021 · GitHub

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// A Simple Merge based O(n) solution
// to find median of two sorted arrays
class GFG{

// Function to calculate median
static int getMedian(int ar1[], int ar2[],
                     int n, int m)
{

    // Current index of input array ar1[]
    int i = 0;

    // Current index of input array ar2[]
    int j = 0;
    int count;
    int m1 = -1, m2 = -1;

    // Since there are (n+m) elements,
    // There are following two cases
    // if n+m is odd then the middle
    //index is median i.e. (m+n)/2
    if ((m + n) % 2 == 1)
    {
        for(count = 0;
            count <= (n + m) / 2;
            count++)
        {
            if (i != n && j != m)
            {
                m1 = (ar1[i] > ar2[j]) ?
                      ar2[j++] : ar1[i++];
            }
            else if (i < n)
            {
                m1 = ar1[i++];
            }

            // for case when j<m,
            else
            {
                m1 = ar2[j++];
            }
        }
        return m1;
    }

    // median will be average of elements
    // at index ((m+n)/2 - 1) and (m+n)/2
    // in the array obtained after merging
    // ar1 and ar2
    else
    {
        for(count = 0;
            count <= (n + m) / 2;
            count++)
        {
            m2 = m1;
            if (i != n && j != m)
            {
                m1 = (ar1[i] > ar2[j]) ?
                      ar2[j++] : ar1[i++];
            }
            else if (i < n)
            {
                m1 = ar1[i++];
            }

            // for case when j<m,
            else
            {
                m1 = ar2[j++];
            }
        }
        return (m1 + m2) / 2;
    }
}

// Driver code
public static void main(String[] args)
{
    int ar1[] = { 900 };
    int ar2[] = { 5, 8, 10, 20 };

    int n1 = ar1.length;
    int n2 = ar2.length;

    System.out.println(getMedian(ar1, ar2, n1, n2));
}
}

// Output
//10