Изменения
→Варианты решения
== Варианты решения ==
=== Наивное решение ===
Сольем два массива и просто возьмем элемент с индексом <tex>k- 1</tex>. Сливание будет выполнено за <tex>O(n + m)</tex>.
=== Чуть менее наивное решение ===
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k- 1)</tex>-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
=== Совсем не наивное решение ===
Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях <tex>k</tex>. Следующее решение работает за <tex>O(log(n) + log(m))</tex>.
Чтобы получить логарифмическую сложность, будем использовать бинарный поиск, который вдвое сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации вдвое сокращать круг поиска в каждом из массивов.
