Изменения

Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j</tex> {{---}} <tex>1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j</tex> {{---}} <tex>2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j</tex> {{---}} <tex>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</tex> {{---}} <tex>1]</tex>, а в массиве <tex>B</tex> {{---}} <tex>[0, j</tex> {{---}} <tex>1]</tex>. Также, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i</tex> {{---}} <tex>1]</tex>. Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i</tex> {{---}} <tex>1]</tex>, в массиве <tex>B</tex> {{---}} <tex>[j + 1, m</tex> {{---}} <tex>1]</tex>.

'''int''' findKthOrderStatistic('''int[]''' A, '''int''' n, '''int[]''' B, '''int''' m, '''int''' k):

'''int''' i = n * (k - 1) / (n + m)

'''int''' j = (k - 1) - i

'''int''' Ai_left = ((i == 0) ? INT_MIN : A[i-1])

'''int''' Bj_left = ((j == 0) ? INT_MIN : B[j-1])

'''if''' (Bj_left < Ai and Ai < Bj):

'''return''' Ai

'''return''' Bj

'''if''' (Ai < Bj):

'''else'''

'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)