577
правок
Изменения
→Совсем не наивное решение
<tex>\mathtt{findKthOrderStatistic}</tex>('''int*''' A, '''int''' n, '''int*''' B, '''int''' m, '''int''' k):
'''int''' i = n / 2
'''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
'''if''' (j >= m):
'''return''' findKthOrderStatistic(A + i + 1, n - i - 1, B, m, k- i - 1)
<font color=green>// чтобы сохранить инвариант, сделаем A[-1] = -INF и B[-1] = -INF </font>
'''int''' Ai_left = ((i == 0) ? INT_MIN : A[i-1])
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
Таким образом первый массив на каждой итерации уменьшается в два раза, и как только он становится маленьким размер массива станет равен единице (это произойдет за <tex>O(\log(n))</tex> операций), мы запустим бинпоиск и найдем ответ за пару сравнений, так как <tex>j = k - 1</tex>O(. Если же размер второго массива станет равным единице раньше этого, то мы будем сокращать размер первого массива в два раза до тех пор, пока <tex>k - n / 2 \log(m))geqslant 0</tex>. Как только это условие перестанет выполняться, мы за несколько сравнений найдем ответ. Итоговая асимптотика {{---}} <tex>O(\log(n) + \log(m))</tex>.
==См. также==
