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