Нахождение медианы двух массивов

[RawonaM]

Даны два массива чисел X[1..n] и Y[1..n], оба сортированные.
Нужно дать алгоритм со сложностью O(lg n) находящий медиану всех 2n чисел из обоих массивов.

Мое решение основывается на том, что медиана двух массивов находится между медианами каждого массива по отдельности, т.е. если m - это медиана всех чисел, то X[n/2]<m<=Y[n/2] или Y[n/2]<m<=X[n/2]. Доказательство: если X[n/2]<m и Y[n/2]<m, то количество чисел меньших или равных m из обоих массивов превышает 2n/2, поэтому m не может быть медианой. Аналогично если обе медианы больше m.
Прим.: под медианой понимается нижняя медиана, а деление всегда без остатка.

Поэтому можно предложить такой алгоритм (псевдокод):
Find-M(A,p,r,B,s,t)
    if r-p == 0
        return min(A[p],B)       

    m1 = A[(r+p)/2]
    m2 = B[(t+s)/2]

    if m1 >= m2
         return Find-M(A,p,(r+p)/2,B,(t+s+1)/2,t)
    else
         return Find-M(A,(r+p+1)/2,r,B,s,(t+s)/2)



Что скажете, есть ли тут ошибки?

[Alone Coder]

Что такое r,p,s,t?

[RawonaM]

Начало и конец (под)массива, который функция получает.

Изначальный вызов будет Find-M(X,1,n,Y,1,n).

[RawonaM]

Не, что-то не клеится. Надо исправлять.

[RawonaM]

Кажется допилил. Исправил в изначальном сообщении. Вот код на пюфоне:

Код Выделить Развернуть

def FindM(A,p,r,B,s,t):
    print A[p:r+1]
    print B[s:t+1]
    print '---'
    if (r == p):
        return min(A[p],B[s])

    m1 = A[(r+p)/2]
    m2 = B[(t+s)/2]

    if (m1 >= m2):
        return FindM(A,p,(r+p)/2,B,(t+s+1)/2,t)
    else:
        return FindM(A,(r+p+1)/2,r,B,s,(t+s)/2)

X = ['',1,4,5,7]
Y = ['',3,6,9,10]
print FindM(X,1,len(X)-1,Y,1,len(Y)-1)


Что скажете, будет ли всегда работать?



Еще есть задачка как обобщение этому случаю: нужно написать алгоритм, который находит k-ное значение по возрастанию из таких же двух массивов. Cложность алгоритма должна быть O(lg min(k,2n-k)).

Можно решать в лоб, но раз уже есть Find-M, то берем и делаем так:

Код Выделить Развернуть

def FindK(k,A,p,r,B,s,t):
    n = (r-p)+1     # the length of A or B
    if k <= n:
        # leave only the first k elements in each array,
        # now the k-th element of the old arrays is the median of the new arrays
        return FindM(A,p,p+k-1,B,s,s+k-1)
    else:
        # leave only the last k elements in each array, again the k-th element
        # of the old arrays is the is the upper median of the new ones
        return FindUM(A,r-(2*n-k)+1,r,B,t-(2*n-k)+1,t)


Верхняя медиана соответственно:

Код Выделить Развернуть

def FindUM(A,p,r,B,s,t):
    if (r == p):
        return max(A[p],B[s])

    m1 = A[(r+p+1)/2]
    m2 = B[(t+s+1)/2]

    if (m1 >= m2):
        return FindUM(A,p,(r+p)/2,B,(t+s+1)/2,t)
    else:
        return FindUM(A,(r+p+1)/2,r,B,s,(t+s)/2)


Как вам?

[RawonaM]

Меня что смущает. Я нашел ответы к книге, а там в ответах алгоритм нахождения медианы намного-намного запутаннее... Не могу сказать, что такого не случается, но прямо такая разница чтобы...
Потом выложу алгоритм из ответов.

[Alone Coder]

Что скажете, будет ли всегда работать?

Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Я вообще не представляю, как тут возможно логарифмическое время.
По идее надо начать со сравнения k-го элемента первого массива с 1-м элементом второго массива. Вопрос, какое оптимальное k. Дальше - хуже.

[RawonaM]

Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.

Пример можете привести, где это не так? Под серединой вы тут медиану имеете в виду? Напоминаю: массивы отсортированы.

[RawonaM]

Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.

Все-таки медианы обоих массивов не могут быть больше медианы общего массива. Вы наверное забыли про отсортированность.

[Alone Coder]

Действительно.

[RawonaM]

А в книге ответ на вопрос про нахождение медианы вот такой: