Нахождение медианы 2 массивов одинакового размера - алгоритм O (log n) не дает правильного результата

Question

Я пытаюсь решить проблему вычисления медианы двух объединенных отсортированных массивов одинакового размера с разными элементами.

Источник алгоритма: https://www.geeksforgeeks.org/median-of-two-sorted-arrays/ Этот алгоритм используется в нескольких источниках через inte rnet в качестве решения O (log n). Однако я не думаю, что это работает для примера, который я составил.

Мой контрпример:

У нас есть 2 отсортированных массива без дубликатов:

[2,3,12,14] & [1,5,8,9]

Объединенный отсортированный массив: a = [1,2,3,5,8,9,12,14] Медиана: 13/2 = 6.5

В соответствии с алгоритмом:

Медиана [2,3,12,14] равна (3+12)/2= 7.5 = m1

Медиана [1,5,8,9] равна (5+8)/2 = 6.5 = m2

Мы видим m1>m2. Таким образом, следуя алгоритму, мы рассмотрим первую половину первого массива и вторую половину второго массива. У нас есть a1 = [2,3] и a2 = [8,9].

Теперь мы достигли базового случая, и у нас есть результат (max(a1[0],a2[0]) + min(a1[1],a2[1]))/2 = 8+3=11/2=5.5, который явно не 6.5.

Это единственный алгоритм, который я вижу, который имеет решение O (log n) но это кажется ущербным. Я что-то упускаю здесь?

Answer 1

Чтобы всегда давать один и тот же результат первого метода, второй должен заканчиваться одинаковыми номерами в последней итерации.

Например, приведенный пример должен привести к 6,5

[2, 3, 12, 14], [1, 5, 8, 9] → [1, 2, 3, 5 , 8 , 9, 12, 14] → (5 + 8) / 2 → 6,5

Чтобы гарантировать, что при делении диапазонов с четным числом элементов вы должны добавить нижеприведенный элемент посередине:

[2, 3 , 12 , 14], [1, 5 , 8 , 9] → [2, 3, 12 ], [ 5 , 8 , 9] → [3, 12], [5, 8] → 6,5

As на самом деле соответствующая часть кода на странице, на которую вы ссылаетесь, это

int getMedian(int ar1[],  
              int ar2[], int n)
{
    // ...
    if (m1 < m2) 
    { 
        if (n % 2 == 0) 
            return getMedian(ar1 + n / 2 - 1,    // <- Note the difference
                             ar2, n - n / 2 + 1); 
        return getMedian(ar1 + n / 2,            // <-
                         ar2, n - n / 2); 
    } 

    if (n % 2 == 0) 
        return getMedian(ar2 + n / 2 - 1,        // The same here
                         ar1, n - n / 2 + 1); 
    return getMedian(ar2 + n / 2,  
                     ar1, n - n / 2); 

Answer 2

Не отследите вручную, запустите код.

Версии обоих алгоритмов Python дают правильный ответ для вашего попытанного контрпримера.

Я не могу обещать, что все реализации работают правильно. Но помните, что всегда гораздо более вероятно, что вы допустили ошибку, чем то, что было рассмотрено многими неправильно. (Не всегда неправильно, именно поэтому я выполнил реальный код на вашем примере.) И вероятность ошибки go значительно возрастает, когда вы пытаетесь отследить код вручную.