Разработка алгоритма задач Clog n[C++ code]

Question

Два отсортированных массива целых чисел A[1..N] а также B[1..N] предоставляются в порядке возрастания.

Q: Дизайн O(log N)-time алгоритм нахождения медианы всех 2N целых чисел. N, возможно, не сила 2.

Чтобы упростить задачу, мы можем предположить, O(1) алгоритм, который возвращает m такой что:

2^m < N <  2^m+1

Мои проблемы:

1. N не может быть сила 2, что это значит? (Понимать)
2. Я не знаю, как изменить вход и сделать длину до степени 2 после того, как нашел min а также max элементы из обоих массивов A а также B ,

Answer 1

Вы можете решить это в O(logN) время с использованием подхода бинарного стиля поиска. Рассмотрим следующие два массива:

1 1 2 2 3
1 2 3 4 5

Теперь комбинированная медиана составляет:

1 1 1 2 2 2 3 3 4 5 => 2

Посмотрим, как мы можем его найти. Начните с предположения, что медиана является центром каждого массива:

1 1 2 2 3 => 2
1 2 3 4 5 => 3

Логически, мы знаем, что комбинированное медиана не может быть меньше 2 или больше 3. Скорее, оно должно находиться где-то между этими двумя значениями. Таким образом, мы можем отбросить все в первом массиве меньше 2 и все во втором массиве больше 3. Это не повлияет на положение медианы, потому что мы отбрасываем равное количество элементов с обеих сторон от того места, где объединенная медиана, Концептуально это оставляет нас с:

2 2 3 => 2
1 2 3 => 2

Теперь у нас уже есть согласующая медиана, но основная идея состоит в том, чтобы отбрасывать половину записей в каждом из двух массивов, пока у нас не будет единственной медианы.

Этот алгоритм будет выполнять так же, как бинарный поиск, который O(logN),