577
правок
Изменения
→Совсем не наивное решение
<font color=green>// во избежание коллизий перед вызовом функции проинициализируем A[n] = +INF, B[m] = +INF </font>
'''int''' findKthOrderStatistic('''int*''' A, '''int''' n, '''int*''' B, '''int''' m, '''int''' k):
'''if''' (n == 1):
'''int''' tmp = binSearch(B, m, A[0]) <font color=green>// вернет позицию, на которой должен стоять элемент A[0] в массиве B
'''if''' (tmp > k):
'''return''' B[k - 1]
'''else if''' (tmp == k):
'''return''' A[0]
'''else'''
'''return''' B[k - 2]
'''int''' i = n / 2
'''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
'''else'''
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
Таким образом первый массив на каждой итерации уменьшается в два раза, как только он становится маленьким (это произойдет за <tex>O(log(n))</tex> операций), мы запустим бинпоиск и найдем ответ за <tex>O(log(m))</tex>. Итоговая асимптотика - <tex>O(log(n) + log(m))</tex>.
==См. также==
