divide and conquer - найти медиану между двумя массивами одинакового размера, которые содержат уникальные элементы?

Question

Я пытаюсь решить проблему именно так: nth smallest number among two databases of size n each using divide and conquer

Из того, что я мог понять, то «по сравнению медианы/медиану медиан» алгоритм даст нам решение? Мой вопрос: правильно ли я это понимаю.

array 1: [7 8 6 5 3] 
array 2: [4 10 1 2 9] 

Во-первых, найти медиану для каждого. мы можем сделать это, запросив при k = n/2, где n - размер этого массива. Будучи 3-м наименьшим элементом в этом случае, это дает нам 6 для первого массива (назовите это m1) и 4 для второго массива (назовите это m2).

С m1 > m2 создайте 2 массива с использованием элементов, которые меньше, чем m1 и больше m2 в этом массиве.

array 1: [5 3] 
array 2: [10 9] 

^Как мы находим элементы, которые меньше, чем m1 и больше м2? Не могли бы мы взять m1 и m2 и сравнить их с каждым элементом в их соответствующих массивах? Я знаю, что это работает, когда оба массива отсортированы, но сортировка их сначала позволит нам получить запросы O (log (n))?

Я предполагаю, что мы можем продолжать использовать наш специальный запрос (можем ли мы?) получить наименьший элемент k = n/2 (медианный) для этого конкретного массива. Если это так, мы запрашиваем для k = n/2 = 1, оставляя нас с новыми m1 = 3, m2 = 9.

m1 < m2, поэтому мы создаем 2 массива с использованием элементов, превышающих m1 и меньше m2 в этом массиве.

Поскольку в массиве 2 нет элементов, которые меньше m2 = 9, мы оставляем только один массив с одним элементом больше m1 = 3.

< [5] - это средний

Я также заинтересован в том, доказательства правильности (что это находит медиану) по индукции.

Answer 1

Мейдан медианного (O) -медианна медианного алгоритма на самом деле разбивает массив таким образом, чтобы элементы перед ним были меньше его и после него были больше его.

Когда вы рекурсия с медианой медиан в качестве опоры, вы разбиение массива, так что он выглядит как

(элементы меньше, чем медиана) - р - (элементы больше, чем медиана)

О правильности, когда вы сначала запрашиваете k = n/2. Вы получаете m1 и m2 (m1> m2). Теперь вы знаете, что существует более n элементов, которые меньше m1. поэтому элементы, следующие за ним, никогда не будут кандидатами для медианы.
Аналогичным образом элементы до м2. впереди их больше, чем n элементов, поэтому они никогда не станут кандидатами на медианную. Таким образом, медиана должна лежать где-то во второй половине второго массива и в первой половине первого массива.

Но теперь, когда вы рекурсируете, вы должны иметь в виду, что у вас есть n/2 элемента для второго массива, для которого требуется, поэтому вам нужно найти элемент, который будет занимать n/2-ю позицию в сортированном объединении двух массивы (вторая половина и первая половина).

Это кажется асимптотически оптимальным, поскольку вы всегда уменьшаете размер массивов, которые вы возвращаете на половину. что-то вроде O (n) + O (n/2) + O (n/4) ... = O (n).

Для отсортированных массивов вы можете сделать это O (logn).