Поиск k-ой порядковой статистики в двух массивах

Постановка задачи

Пусть даны два отсортированных массива [math]A[/math] и [math]B[/math] размерами [math]n[/math] и [math]m[/math] соответственно. Требуется найти [math]k[/math]-ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны.

Варианты решения

Наивное решение за [math]O(n + m)[/math]

Сольем два массива и просто возьмем элемент с индексом [math]k[/math]. Сливание будет выполнено за O(n + m).