میانه دو آرایه مرتب شده با اندازه یکسان — به زبان ساده

1// A Simple Merge based O(n)  
2// solution to find median of 
3// two sorted arrays 
4#include <bits/stdc++.h> 
5using namespace std; 
6  
7/* This function returns  
8median of ar1[] and ar2[]. 
9Assumptions in this function: 
10Both ar1[] and ar2[]  
11are sorted arrays 
12Both have n elements */
13int getMedian(int ar1[], 
14              int ar2[], int n) 
15{ 
16    int i = 0; /* Current index of  
17                  i/p array ar1[] */
18    int j = 0; /* Current index of  
19                  i/p array ar2[] */
20    int count; 
21    int m1 = -1, m2 = -1; 
22  
23    /* Since there are 2n elements,  
24    median will be average of elements  
25    at index n-1 and n in the array  
26    obtained after merging ar1 and ar2 */
27    for (count = 0; count <= n; count++) 
28    { 
29        /* Below is to handle case where  
30           all elements of ar1[] are 
31           smaller than smallest(or first) 
32           element of ar2[]*/
33        if (i == n) 
34        { 
35            m1 = m2; 
36            m2 = ar2[0]; 
37            break; 
38        } 
39  
40        /*Below is to handle case where  
41          all elements of ar2[] are 
42          smaller than smallest(or first) 
43          element of ar1[]*/
44        else if (j == n) 
45        { 
46            m1 = m2; 
47            m2 = ar1[0]; 
48            break; 
49        } 
50  
51        if (ar1[i] < ar2[j]) 
52        { 
53            /* Store the prev median */
54            m1 = m2;  
55            m2 = ar1[i]; 
56            i++; 
57        } 
58        else
59        { 
60            /* Store the prev median */
61            m1 = m2;  
62            m2 = ar2[j]; 
63            j++; 
64        } 
65    } 
66  
67    return (m1 + m2)/2; 
68} 
69  
70// Driver Code 
71int main() 
72{ 
73    int ar1[] = {1, 12, 15, 26, 38}; 
74    int ar2[] = {2, 13, 17, 30, 45}; 
75  
76    int n1 = sizeof(ar1) / sizeof(ar1[0]); 
77    int n2 = sizeof(ar2) / sizeof(ar2[0]); 
78    if (n1 == n2) 
79        cout << "Median is " 
80             << getMedian(ar1, ar2, n1) ; 
81    else
82        cout << "Doesn't work for arrays" 
83             << " of unequal size" ; 
84    getchar(); 
85    return 0; 
86} 
87  
88// This code is contributed  
89// by Shivi_Aggarwal

1// A Simple Merge based O(n) solution to find median of 
2// two sorted arrays 
3#include <stdio.h> 
4  
5/* This function returns median of ar1[] and ar2[]. 
6   Assumptions in this function: 
7   Both ar1[] and ar2[] are sorted arrays 
8   Both have n elements */
9int getMedian(int ar1[], int ar2[], int n) 
10{ 
11    int i = 0;  /* Current index of i/p array ar1[] */
12    int j = 0; /* Current index of i/p array ar2[] */
13    int count; 
14    int m1 = -1, m2 = -1; 
15  
16    /* Since there are 2n elements, median will be average 
17     of elements at index n-1 and n in the array obtained after 
18     merging ar1 and ar2 */
19    for (count = 0; count <= n; count++) 
20    { 
21        /*Below is to handle case where all elements of ar1[] are 
22          smaller than smallest(or first) element of ar2[]*/
23        if (i == n) 
24        { 
25            m1 = m2; 
26            m2 = ar2[0]; 
27            break; 
28        } 
29  
30        /*Below is to handle case where all elements of ar2[] are 
31          smaller than smallest(or first) element of ar1[]*/
32        else if (j == n) 
33        { 
34            m1 = m2; 
35            m2 = ar1[0]; 
36            break; 
37        } 
38  
39        if (ar1[i] < ar2[j]) 
40        { 
41            m1 = m2;  /* Store the prev median */
42            m2 = ar1[i]; 
43            i++; 
44        } 
45        else
46        { 
47            m1 = m2;  /* Store the prev median */
48            m2 = ar2[j]; 
49            j++; 
50        } 
51    } 
52  
53    return (m1 + m2)/2; 
54} 
55  
56/* Driver program to test above function */
57int main() 
58{ 
59    int ar1[] = {1, 12, 15, 26, 38}; 
60    int ar2[] = {2, 13, 17, 30, 45}; 
61  
62    int n1 = sizeof(ar1)/sizeof(ar1[0]); 
63    int n2 = sizeof(ar2)/sizeof(ar2[0]); 
64    if (n1 == n2) 
65        printf("Median is %d", getMedian(ar1, ar2, n1)); 
66    else
67        printf("Doesn't work for arrays of unequal size"); 
68    getchar(); 
69    return 0; 
70}

1// A Simple Merge based O(n) solution  
2// to find median of two sorted arrays 
3  
4class Main 
5{ 
6    // function to calculate median 
7    static int getMedian(int ar1[], int ar2[], int n) 
8    {    
9        int i = 0;   
10        int j = 0;  
11        int count; 
12        int m1 = -1, m2 = -1; 
13       
14        /* Since there are 2n elements, median will  
15           be average of elements at index n-1 and  
16           n in the array obtained after merging ar1  
17           and ar2 */
18        for (count = 0; count <= n; count++) 
19        { 
20            /* Below is to handle case where all  
21              elements of ar1[] are smaller than  
22              smallest(or first) element of ar2[] */
23            if (i == n) 
24            { 
25                m1 = m2; 
26                m2 = ar2[0]; 
27                break; 
28            } 
29       
30            /* Below is to handle case where all  
31               elements of ar2[] are smaller than  
32               smallest(or first) element of ar1[] */
33            else if (j == n) 
34            { 
35                m1 = m2; 
36                m2 = ar1[0]; 
37                break; 
38            } 
39       
40            if (ar1[i] < ar2[j]) 
41            {    
42                /* Store the prev median */
43                m1 = m2;   
44                m2 = ar1[i]; 
45                i++; 
46            } 
47            else
48            { 
49                /* Store the prev median */
50                m1 = m2;   
51                m2 = ar2[j]; 
52                j++; 
53            } 
54        } 
55       
56        return (m1 + m2)/2; 
57    } 
58       
59    /* Driver program to test above function */
60    public static void main (String[] args) 
61    { 
62        int ar1[] = {1, 12, 15, 26, 38}; 
63        int ar2[] = {2, 13, 17, 30, 45}; 
64       
65        int n1 = ar1.length; 
66        int n2 = ar2.length; 
67        if (n1 == n2) 
68            System.out.println("Median is " + 
69                        getMedian(ar1, ar2, n1)); 
70        else
71            System.out.println("arrays are of unequal size"); 
72    }     
73}

1# A Simple Merge based O(n) Python 3 solution  
2# to find median of two sorted lists 
3  
4# This function returns median of ar1[] and ar2[]. 
5# Assumptions in this function: 
6# Both ar1[] and ar2[] are sorted arrays 
7# Both have n elements 
8def getMedian( ar1, ar2 , n): 
9    i = 0 # Current index of i/p list ar1[] 
10      
11    j = 0 # Current index of i/p list ar2[] 
12      
13    m1 = -1
14    m2 = -1
15      
16    # Since there are 2n elements, median 
17    # will be average of elements at index 
18    # n-1 and n in the array obtained after 
19    # merging ar1 and ar2 
20    count = 0
21    while count < n + 1: 
22        count += 1
23          
24        # Below is to handle case where all 
25        # elements of ar1[] are smaller than 
26        # smallest(or first) element of ar2[] 
27        if i == n: 
28            m1 = m2 
29            m2 = ar2[0] 
30            break
31          
32        # Below is to handle case where all  
33        # elements of ar2[] are smaller than 
34        # smallest(or first) element of ar1[] 
35        elif j == n: 
36            m1 = m2 
37            m2 = ar1[0] 
38            break
39        if ar1[i] < ar2[j]: 
40            m1 = m2 # Store the prev median 
41            m2 = ar1[i] 
42            i += 1
43        else: 
44            m1 = m2 # Store the prev median 
45            m2 = ar2[j] 
46            j += 1
47    return (m1 + m2)/2
48  
49# Driver code to test above function 
50ar1 = [1, 12, 15, 26, 38] 
51ar2 = [2, 13, 17, 30, 45] 
52n1 = len(ar1) 
53n2 = len(ar2) 
54if n1 == n2: 
55    print("Median is ", getMedian(ar1, ar2, n1)) 
56else: 
57    print("Doesn't work for arrays of unequal size") 
58  
59# This code is contributed by "Sharad_Bhardwaj".

1// A Simple Merge based O(n) solution  
2// to find median of two sorted arrays 
3using System; 
4class GFG 
5{ 
6    // function to calculate median 
7    static int getMedian(int []ar1,  
8                         int []ar2,  
9                         int n) 
10    {  
11        int i = 0;  
12        int j = 0;  
13        int count; 
14        int m1 = -1, m2 = -1; 
15      
16        // Since there are 2n elements,  
17        // median will be average of  
18        // elements at index n-1 and n in  
19        // the array obtained after  
20        // merging ar1 and ar2 
21        for (count = 0; count <= n; count++) 
22        { 
23            // Below is to handle case  
24            // where all elements of ar1[]   
25            // are smaller than smallest 
26            // (or first) element of ar2[]  
27            if (i == n) 
28            { 
29                m1 = m2; 
30                m2 = ar2[0]; 
31                break; 
32            } 
33      
34            /* Below is to handle case where all  
35            elements of ar2[] are smaller than  
36            smallest(or first) element of ar1[] */
37            else if (j == n) 
38            { 
39                m1 = m2; 
40                m2 = ar1[0]; 
41                break; 
42            } 
43      
44            if (ar1[i] < ar2[j]) 
45            {  
46                // Store the prev median  
47                m1 = m2;  
48                m2 = ar1[i]; 
49                i++; 
50            } 
51            else
52            { 
53                // Store the prev median  
54                m1 = m2;  
55                m2 = ar2[j]; 
56                j++; 
57            } 
58        } 
59      
60        return (m1 + m2)/2; 
61    } 
62      
63    // Driver Code 
64    public static void Main () 
65    { 
66        int []ar1 = {1, 12, 15, 26, 38}; 
67        int []ar2 = {2, 13, 17, 30, 45}; 
68      
69        int n1 = ar1.Length; 
70        int n2 = ar2.Length; 
71        if (n1 == n2) 
72            Console.Write("Median is " + 
73                        getMedian(ar1, ar2, n1)); 
74        else
75            Console.Write("arrays are of unequal size"); 
76    }  
77}

1<?php 
2// A Simple Merge based O(n) solution  
3// to find median of two sorted arrays 
4  
5// This function returns median of  
6// ar1[] and ar2[]. Assumptions in  
7// this function: Both ar1[] and ar2[]  
8// are sorted arrays Both have n elements  
9function getMedian($ar1, $ar2, $n) 
10{ 
11    // Current index of i/p array ar1[] 
12    $i = 0;  
13      
14    // Current index of i/p array ar2[] 
15    $j = 0;  
16    $count; 
17    $m1 = -1; $m2 = -1; 
18  
19    // Since there are 2n elements,  
20    // median will be average of elements  
21    // at index n-1 and n in the array  
22    // obtained after merging ar1 and ar2  
23    for ($count = 0; $count <= $n; $count++) 
24    { 
25        // Below is to handle case where  
26        // all elements of ar1[] are smaller 
27        // than smallest(or first) element of ar2[] 
28        if ($i == $n) 
29        { 
30            $m1 = $m2; 
31            $m2 = $ar2[0]; 
32            break; 
33        } 
34  
35        // Below is to handle case where all  
36        // elements of ar2[] are smaller than  
37        // smallest(or first) element of ar1[] 
38        else if ($j == $n) 
39        { 
40            $m1 = $m2; 
41            $m2 = $ar1[0]; 
42            break; 
43        } 
44  
45        if ($ar1[$i] < $ar2[$j]) 
46        { 
47            // Store the prev median 
48            $m1 = $m2;  
49            $m2 = $ar1[$i]; 
50            $i++; 
51        } 
52        else
53        { 
54            // Store the prev median 
55            $m1 = $m2; 
56            $m2 = $ar2[$j]; 
57            $j++; 
58        } 
59    } 
60  
61    return ($m1 + $m2) / 2; 
62} 
63  
64// Driver Code 
65$ar1 = array(1, 12, 15, 26, 38); 
66$ar2 = array(2, 13, 17, 30, 45); 
67  
68$n1 = sizeof($ar1); 
69$n2 = sizeof($ar2); 
70if ($n1 == $n2) 
71    echo("Median is " .  
72          getMedian($ar1, $ar2, $n1)); 
73else
74    echo("Doesn't work for arrays".  
75         "of unequal size"); 
76  
77// This code is contributed by Ajit. 
78?>

1// A divide and conquer based  
2// efficient solution to find  
3// median of two sorted arrays  
4// of same size. 
5#include<bits/stdc++.h> 
6using namespace std; 
7  
8/* to get median of a 
9   sorted array */
10int median(int [], int);  
11  
12/* This function returns median  
13   of ar1[] and ar2[]. 
14Assumptions in this function: 
15    Both ar1[] and ar2[] are  
16    sorted arrays 
17    Both have n elements */
18int getMedian(int ar1[],  
19              int ar2[], int n) 
20{ 
21    /* return -1 for  
22       invalid input */
23    if (n <= 0) 
24        return -1; 
25    if (n == 1) 
26        return (ar1[0] +  
27                ar2[0]) / 2; 
28    if (n == 2) 
29        return (max(ar1[0], ar2[0]) +  
30                min(ar1[1], ar2[1])) / 2; 
31  
32    /* get the median of  
33       the first array */
34    int m1 = median(ar1, n);  
35      
36    /* get the median of  
37       the second array */
38    int m2 = median(ar2, n);  
39  
40    /* If medians are equal then  
41       return either m1 or m2 */
42    if (m1 == m2) 
43        return m1; 
44  
45    /* if m1 < m2 then median must  
46       exist in ar1[m1....] and 
47                ar2[....m2] */
48    if (m1 < m2) 
49    { 
50        if (n % 2 == 0) 
51            return getMedian(ar1 + n / 2 - 1,  
52                             ar2, n - n / 2 + 1); 
53        return getMedian(ar1 + n / 2,  
54                         ar2, n - n / 2); 
55    } 
56  
57    /* if m1 > m2 then median must  
58       exist in ar1[....m1] and  
59                ar2[m2...] */
60    if (n % 2 == 0) 
61        return getMedian(ar2 + n / 2 - 1,  
62                         ar1, n - n / 2 + 1); 
63    return getMedian(ar2 + n / 2,  
64                     ar1, n - n / 2); 
65} 
66  
67/* Function to get median  
68   of a sorted array */
69int median(int arr[], int n) 
70{ 
71    if (n % 2 == 0) 
72        return (arr[n / 2] +  
73                arr[n / 2 - 1]) / 2; 
74    else
75        return arr[n / 2]; 
76} 
77  
78// Driver code 
79int main() 
80{ 
81    int ar1[] = {1, 2, 3, 6}; 
82    int ar2[] = {4, 6, 8, 10}; 
83    int n1 = sizeof(ar1) /  
84             sizeof(ar1[0]); 
85    int n2 = sizeof(ar2) /  
86             sizeof(ar2[0]); 
87    if (n1 == n2) 
88        cout << "Median is "
89             << getMedian(ar1, ar2, n1); 
90    else
91        cout << "Doesn't work for arrays " 
92             << "of unequal size"; 
93    return 0; 
94} 
95  
96// This code is contributed 
97// by Shivi_Aggarwal

1// A divide and conquer based efficient solution to find median 
2// of two sorted arrays of same size. 
3#include<bits/stdc++.h> 
4using namespace std; 
5  
6int median(int [], int); /* to get median of a sorted array */
7  
8/* This function returns median of ar1[] and ar2[]. 
9   Assumptions in this function: 
10   Both ar1[] and ar2[] are sorted arrays 
11   Both have n elements */
12int getMedian(int ar1[], int ar2[], int n) 
13{ 
14    /* return -1  for invalid input */
15    if (n <= 0) 
16        return -1; 
17    if (n == 1) 
18        return (ar1[0] + ar2[0])/2; 
19    if (n == 2) 
20        return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2; 
21  
22    int m1 = median(ar1, n); /* get the median of the first array */
23    int m2 = median(ar2, n); /* get the median of the second array */
24  
25    /* If medians are equal then return either m1 or m2 */
26    if (m1 == m2) 
27        return m1; 
28  
29    /* if m1 < m2 then median must exist in ar1[m1....] and 
30        ar2[....m2] */
31    if (m1 < m2) 
32    { 
33        if (n % 2 == 0) 
34            return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1); 
35        return getMedian(ar1 + n/2, ar2, n - n/2); 
36    } 
37  
38    /* if m1 > m2 then median must exist in ar1[....m1] and 
39        ar2[m2...] */
40    if (n % 2 == 0) 
41        return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1); 
42    return getMedian(ar2 + n/2, ar1, n - n/2); 
43} 
44  
45/* Function to get median of a sorted array */
46int median(int arr[], int n) 
47{ 
48    if (n%2 == 0) 
49        return (arr[n/2] + arr[n/2-1])/2; 
50    else
51        return arr[n/2]; 
52} 
53  
54/* Driver program to test above function */
55int main() 
56{ 
57    int ar1[] = {1, 2, 3, 6}; 
58    int ar2[] = {4, 6, 8, 10}; 
59    int n1 = sizeof(ar1)/sizeof(ar1[0]); 
60    int n2 = sizeof(ar2)/sizeof(ar2[0]); 
61    if (n1 == n2) 
62        printf("Median is %d", getMedian(ar1, ar2, n1)); 
63    else
64        printf("Doesn't work for arrays of unequal size"); 
65    return 0; 
66} 

1// A Java program to divide and conquer based  
2// efficient solution to find  
3// median of two sorted arrays  
4// of same size. 
5import java.util.*; 
6class GfG {  
7  
8/* This function returns median  
9of ar1[] and ar2[].  
10Assumptions in this function:  
11    Both ar1[] and ar2[] are  
12    sorted arrays  
13    Both have n elements */
14static int getMedian(int ar1[], int ar2[], int n)  
15{  
16    /* return -1 for  
17    invalid input */
18    if (n <= 0)  
19        return -1;  
20    if (n == 1)  
21        return (ar1[0] + ar2[0]) / 2;  
22    if (n == 2)  
23        return (Math.max(ar1[0], ar2[0]) + Math.min(ar1[1], ar2[1])) / 2;  
24  
25    /* get the median of  
26    the first array */
27    int m1 = median(ar1, n);  
28      
29    /* get the median of  
30    the second array */
31    int m2 = median(ar2, n);  
32  
33    /* If medians are equal then  
34    return either m1 or m2 */
35    if (m1 == m2)  
36        return m1;  
37  
38    /* if m1 < m2 then median must  
39    exist in ar1[m1....] and  
40                ar2[....m2] */
41    if (m1 < m2)  
42    {  
43        if (n % 2 == 0)  
44            return getMedian(ar1 + n / 2 - 1, ar2, n - n / 2 + 1);  
45        return getMedian(ar1 + n / 2, ar2, n - n / 2);  
46    }  
47  
48    /* if m1 > m2 then median must  
49    exist in ar1[....m1] and  
50                ar2[m2...] */
51    if (n % 2 == 0)  
52        return getMedian(ar2 + n / 2 - 1, ar1, n - n / 2 + 1);  
53    return getMedian(ar2 + n / 2, ar1, n - n / 2);  
54}  
55  
56/* Function to get median  
57of a sorted array */
58static int median(int arr[], int n)  
59{  
60    if (n % 2 == 0)  
61        return (arr[n / 2] + arr[n / 2 - 1]) / 2;  
62    else
63        return arr[n / 2];  
64}  
65  
66// Driver code  
67public static void main(String[] args)  
68{  
69    int ar1[] = {1, 2, 3, 6};  
70    int ar2[] = {4, 6, 8, 10};  
71    int n1 = ar1.length;  
72    int n2 = ar2.length;  
73    if (n1 == n2)  
74        System.out.println("Median is " + getMedian(ar1, ar2, n1));  
75    else
76        System.out.println("Doesn't work for arrays "+ "of unequal size");  
77} 
78}

1# using divide and conquer we divide 
2# the 2 arrays accordingly recursively 
3# till we get two elements in each  
4# array, hence then we calculate median 
5  
6#condition len(arr1)=len(arr2)=n 
7def getMedian(arr1, arr2, n):  
8      
9    # there is no element in any array 
10    if n == 0:  
11        return -1
12          
13    # 1 element in each => median of  
14    # sorted arr made of two arrays will     
15    elif n == 1:  
16        # be sum of both elements by 2 
17        return (arr1[0]+arr2[1])/2
18          
19    # Eg. [1,4] , [6,10] => [1, 4, 6, 10] 
20    # median = (6+4)/2     
21    elif n == 2:  
22        # which implies median = (max(arr1[0], 
23        # arr2[0])+min(arr1[1],arr2[1]))/2 
24        return (max(arr1[0], arr2[0]) + 
25                min(arr1[1], arr2[1])) / 2
26      
27    else: 
28        #calculating medians      
29        m1 = median(arr1, n) 
30        m2 = median(arr2, n) 
31          
32        # then the elements at median  
33        # position must be between the  
34        # greater median and the first  
35        # element of respective array and  
36        # between the other median and  
37        # the last element in its respective array. 
38        if m1 > m2: 
39              
40            if n % 2 == 0: 
41                return getMedian(arr1[:int(n / 2) + 1], 
42                        arr2[int(n / 2) - 1:], int(n / 2) + 1) 
43            else: 
44                return getMedian(arr1[:int(n / 2) + 1],  
45                        arr2[int(n / 2):], int(n / 2) + 1) 
46          
47        else: 
48            if n % 2 == 0: 
49                return getMedian(arr1[int(n / 2 - 1):], 
50                        arr2[:int(n / 2 + 1)], int(n / 2) + 1) 
51            else: 
52                return getMedian(arr1[int(n / 2):],  
53                        arr2[0:int(n / 2) + 1], int(n / 2) + 1) 
54  
55 # function to find median of array 
56def median(arr, n): 
57    if n % 2 == 0: 
58        return (arr[int(n / 2)] +
59                arr[int(n / 2) - 1]) / 2
60    else: 
61        return arr[int(n/2)] 
62  
63      
64# Driver code 
65arr1 = [1, 2, 3, 6] 
66arr2 = [4, 6, 8, 10] 
67n = len(arr1) 
68print(int(getMedian(arr1,arr2,n))) 
69  
70# This code is contributed by 
71# baby_gog9800