577
правок
Изменения
→Варианты решения
Таким образом первый массив на каждой итерации уменьшается в два раза, как только он становится маленьким (это произойдет за <tex>O(log(n))</tex> операций), мы запустим бинпоиск и найдем ответ за <tex>O(log(m))</tex>. Итоговая асимптотика {{---}} <tex>O(log(n) + log(m))</tex>.
=== Еще одно решение ===
В первом массиве выберем серединный элемент <tex>(i = n / 2)</tex> и бинпоиском найдем во втором массиве позицию <tex>j</tex>, на которой должен стоять (или стоит) элемент <tex>(a[i] - 1)</tex>. Если <tex>i + j = k - 2</tex>, то мы нашли <tex>k</tex>-ую порядковую статистику {{---}} это элемент <tex>a[i]</tex>. Иначе, если <tex>i + j > k - 2</tex>, то далее ищем в массиве <tex>A</tex> в диапазоне индексов <tex>[0, i</tex> {{---}} <tex>1]</tex>, а если <tex>i + j < k - 2</tex>, то в диапазоне индексов <tex>[i + 1, n - 1]</tex>.
==См. также==
