Алгоритм: Медиана два отсортированных массива различных размеров

Question

Вот код, вставленный из here

Я не может понять, что он делает. Я мог бы придумать простой алгоритм для поиска медианы двух отсортированных массивов при объединении. Идея состоит в том, чтобы сравнить медианы (m1, m2) обоих массивов, и если m1 < m2 найти медиану правого первого подмассива из m1 и левого второго подмассива до m2. Следующий код делает это в тех же строках, но я не могу полностью его понять.

double findMedian(int A[], int B[], int l, int r, int nA, int nB) { 
    if (l>r) 
     return findMedian(B, A, max(0, (nA+nB)/2-nA), min(nB, (nA+nB)/2), nB, nA); //What does the min/max do here 
    int i = (l+r)/2; 
    int j = (nA+nB)/2 – i – 1; 
    if (j>=0 && A[i] < B[j]) 
     return findMedian(A, B, i+1, r, nA, nB); 
    else if (j<nB-1 && A[i] > B[j+1]) 
     return findMedian(A, B, l, i-1, nA, nB); 
    else { 
     if ((nA+nB)%2 == 1) return A[i]; 
     else if (i>0) return (A[i]+max(B[j], A[i-1]))/2.0; //I couldn't understand this 
     else return (A[i]+B[j])/2.0; 
    } 
} 

double findMedianSortedArrays(int A[], int n, int B[], int m) { 
    if (n<m) 
     return findMedian(A, B, 0, n-1, n, m); 
    else 
     return findMedian(B, A, 0, m-1, m, n); 
} 

Что делает вторая строка кода? Кроме того, я не мог понять, как последний блок else вернет медиану. будет i индекс содержит медианный, когда n + m является нечетным?

Любая помощь, ссылки или указатели оцениваются.

Answer 1

Это псевдокод за то, что вы хотите сделать.
Я предполагаю, что ar1 и ar2 будут входными массивами и их размер равен n.

Алгоритм:

1) Calculate the medians m1 and m2 of the input arrays ar1[] 
    and ar2[] respectively. 
2) If m1 and m2 both are equal then we are done. 
    return m1 (or m2) 
3) If m1 is greater than m2, then median is present in one 
    of the below two subarrays. 
    a) From first element of ar1 to m1 (ar1[0...|_n/2_|]) 
    b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1]) 
4) If m2 is greater than m1, then median is present in one  
    of the below two subarrays. 
    a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1]) 
    b) From first element of ar2 to m2 (ar2[0...|_n/2_|]) 
5) Repeat the above process until size of both the subarrays 
    becomes 2. 
6) If size of the two arrays is 2 then use below formula to get 
    the median. 
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2  

Теперь вы можете закодировать его на любой язык по вашему выбору.

Надеюсь, это поможет!