Изменения
→Варианты решения
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j - 1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j - 2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j - 2]</tex>), а значит элемент с номером <tex>i</tex> и все до него в массиве <tex>A</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой. Аналогично элемент с индексом <tex>j</tex> и все элементы, стоящие после него, в массиве <tex>B</tex> никогда не будут ответом, так как на позиции <tex>j</tex> будет стоять <tex>(i + j + 2)</tex>-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве <tex>A</tex> только в диапазоне индексов <tex>[i + 1, n - 1]</tex>, а в массиве <tex>B</tex> - <tex>[0, j - 1]</tex>. Также, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i - 1]</tex>. Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i - 1]</tex>, в массиве <tex>B</tex> - <tex>[j + 1, m - 1]</tex>.
'''int''' findKthOrderStatistic('''int[]''' A, '''int''' n, '''int[]''' B, '''int''' m, '''int''' k):
'''int''' i = random(0 .. n - 1)
'''int''' j = (k - 1) - i
<font color=green> // чтобы сохранить инвариант сделаем A[-1] = -INF и A[n] = +INF
B[-1] = -INF и B[m] = +INF </font>
'''int''' Ai_left = ((i == 0) ? INT_MIN : A[i-1])
'''int''' Ai = ((i == n) ? INT_MAX : A[i])
'''int''' Bj_left = ((j == 0) ? INT_MIN : B[j-1])
'''int''' Bj = ((j == m) ? INT_MAX : B[j])
'''if''' (Bj_left < Ai && Ai < Bj):
'''return''' Ai
'''else if''' (Ai_left < Bj && Bj < Ai):
'''return''' Bj
'''if''' (Ai < Bj):
'''return''' findKthOrderStatistic(A + i + 1, n - i - 1, B, j, k- i - 1)
'''else'''
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
