577
правок
Изменения
→Совсем не наивное решение
<font color=green>// во избежание коллизий перед вызовом функции проинициализируем A[n] = +INF, B[m] = +INF </font>
'''int''' findKthOrderStatistic('''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 <= (n + mk / 2)</font> '''intif''' (j >= m): '''return''' findKthOrderStatistic(k A + i + 1, n - i - 1, B, m, k) - i
<font color=green>// чтобы сохранить инвариант, сделаем A[-1] = -INF и B[-1] = -INF </font>
'''int''' Ai_left = ((i == 0) ? INT_MIN : A[i-1])
