Выбор в двух отсортированных массивах

Question

Для двух отсортированных массивов a [] и b [], размеров N1 и N2, соответственно, создайте алгоритм для нахождения k-го по величине ключа. Порядок роста наихудшего времени работы вашего алгоритма должен быть равен  lg (N1 + N2).

В намеки на этот вопрос сказать, что существует два возможных решения:

Подход А: Вычислить средний показатель в a []  и средний показатель в  б [] . Повторить в подзапросе примерно в два раза.

Я уже реализовали это решение (суть которого состоит в изменении размеров/усечения [] и B [] для длины к, находя медиану в каждом, сравнивая их, выбирая соответствующие половины массива - дилинг . угловыми случаи в зависимости от обстоятельств)

другого подхода получил в жизни:

Дизайн алгоритм постоянная времени, чтобы определить, является ли a [я]  является -й по величине ключа. Используйте эту подпрограмму и двоичный поиск.

У меня возникли проблемы с выяснением, как это сделать. Я знаю, что, учитывая только один массив, можно найти, если данный элемент является kth-наибольшим ключом в O (1) раз, просто просматривая индекс этого элемента. Тем не менее, я не уверен, когда два массива, как определить, является ли элемент k-м наибольшим по объединению этих двух массивов.

Answer 1

Если x является к ^ю наибольшего элемента в a ⋃ b, то есть именно k-1 крупные элементы a ⋃ b. Предполагая, что массивы отсортированы в порядке убывания - вам нужно будет отрегулировать арифметику, если они отсортированы по-другому - тогда есть точно i-1 элементов в a, которые больше a[i]; любые оставшиеся большие элементы в объединении должны исходить от b.

Следовательно, a[i] является к ^ю наибольшего элемента в a ⋃ b если есть точно k-i большие элементы в b, так как в этом случае будут i-1 + k-i == k-1 больше элементов в объединении. Поэтому вам нужно сравнить a[i] с b[k-i] и b[k-i+1], чтобы узнать, что, безусловно, O (1).