найти медиану двух отсортированных массивов в логарифмическое время

Question

Я пытаюсь понять this solution к задаче нахождения медианы два отсортированных массивов:

public static double findMedianSortedArrays(int A[], int B[]) { 
    int m = A.length; 
    int n = B.length; 

    if ((m + n) % 2 != 0) // odd 
     return (double) findKth(A, B, (m + n)/2, 0, m - 1, 0, n - 1); 
    else { // even 
     return (findKth(A, B, (m + n)/2, 0, m - 1, 0, n - 1) 
      + findKth(A, B, (m + n)/2 - 1, 0, m - 1, 0, n - 1)) * 0.5; 
    } 
} 

public static int findKth(int A[], int B[], int k, 
    int aStart, int aEnd, int bStart, int bEnd) { 

    int aLen = aEnd - aStart + 1; 
    int bLen = bEnd - bStart + 1; 

    // Handle special cases 
    if (aLen == 0) 
     return B[bStart + k]; 
    if (bLen == 0) 
     return A[aStart + k]; 
    if (k == 0) 
     return A[aStart] < B[bStart] ? A[aStart] : B[bStart]; 

    int aMid = aLen * k/(aLen + bLen); // a's middle count 
    int bMid = k - aMid - 1; // b's middle count 

    // make aMid and bMid to be array index 
    aMid = aMid + aStart; 
    bMid = bMid + bStart; 

    if (A[aMid] > B[bMid]) { 
     k = k - (bMid - bStart + 1); 
     aEnd = aMid; 
     bStart = bMid + 1; 
    } else { 
     k = k - (aMid - aStart + 1); 
     bEnd = bMid; 
     aStart = aMid + 1; 
    } 

    return findKth(A, B, k, aStart, aEnd, bStart, bEnd); 
} 

Первая часть, что я не могу понять, как Средь и bMid определенные в методе findKth, представляют собой средние значения A и B. Я просмотрел несколько примеров вручную, и я понял, что, действительно, после сравнения A [aMid] с B [bMid] осталось только половина от общего количества элементов. Но какова идея определения этих двух индексов? Почему осталось только половина элементов, оставшихся после сравнения A [aMid] и B [bMid]? Может ли кто-нибудь объяснить мне это решение?

Answer 1

Скажите A [] = {1,5,6,7,8,9} и B [] = {2,3,4}, поэтому медиану A [] и B [] должно быть 5, давайте рассмотрим код.

1. findMedianSortedArrays (А, В), т = 6, п = 3
2. findKth (А, В, 4, 0, 5, 0, 2)
   • AMID = 6 * 4/(6 + 3) = 2, bMid = 4-2-1 = 1, как [2] = 6> b [1] = 3, поэтому k = 4- (1-0 + 1) = 2, aEnd = 2, bStart = 2
3. findKth (А, В, 2, 0, 2, 2, 2)
   • AMID = 3 * 2/(3 + 1) = 1, bMid = 2- 1-1 = 0, так как A [1] = 5> B [bMid + bStart] = B [2] = 4, поэтому k = 2 - (2-2 + 1) = 1, aEnd = 1, bStart = 3
4. findKth (А, В, 1, 0, 1, 3, 2)
   • Блен = 0, возврат А [Astart + к] = А [0 + 1] = A [1] = 5

---

Таким образом, общая идея заключается в:

1. Согласно ш восемь из длины массива, получите возможный размер median. (См AMID и bMid)
2. Сравнить А [AMID] и В [bMid], если (А [AMID]> В [bMid]), что означает:
   • Для всех элементов в B [bStart ..bMid], он должен находиться в левой части медианы, это простая часть.
   • И для всех элементов в A [aMid + 1..aEnd] он должен находиться справа от медианного. Это потому, что (aMid-aStart + bMid-bStart) уже равен (aLen + bLen)/2, и в B [aMid + 1..aEnd] могут быть дополнительные элементы, которые в левой части медианы.
   • Итак, мы уменьшаем оба массива до половины размера, поэтому сложность времени выполнения должна быть O (log (m + n)).
3. Так рекурсивно найти мидиана в A [aStart..aMid] и B [bMid + 1..bEnd].