У нас есть два сортированных массива того же размера n. Давайте назовем массив a и b.
Как найти средний элемент в сортированном массиве объединенным a и b?
Example:
n = 4
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
merged = [1, 2, 3, 3, 4, 4, 5, 6]
mid_element = merged[(0 + merged.length - 1) / 2] = merged[3] = 3
Более сложные случаи:
Случай 1:
a = [1, 2, 3, 4]
b = [3, 4, 5, 6]
Случай 2:
a = [1, 2, 3, 4, 8]
b = [3, 4, 5, 6, 7]
Случай 3:
a = [1, 2, 3, 4, 8]
b = [0, 4, 5, 6, 7]
Случай 4:
a = [1, 3, 5, 7]
b = [2, 4, 6, 8]
Время потребовало: O (регистрируют n). Какие-либо идеи?
Посмотрите на середину обоих массивов. Допустим, одно значение меньше, а другое больше.
Отбросить нижнюю половину массива с меньшим значением. Отбросьте верхнюю половину массива с более высоким значением. Теперь у нас осталась половина того, с чего мы начали.
Промойте и повторяйте, пока в каждом массиве не останется только один элемент. Верните меньший из этих двух.
Если два средних значения совпадают, выберите произвольно.
Источники: Блог Билла Ли
Довольно интересная задача. Не уверен насчет O (logn), но решение O ((logn) ^ 2) для меня очевидно. Если вы знаете положение некоторого элемента в первом массиве, вы можете узнать, сколько элементов меньше в обоих массивах, чем это значение (вы уже знаете, сколько меньших элементов находится в первом массиве, и вы можете найти количество меньших элементов во втором массиве, используя двоичный поиск - так что просто суммируйте эти два числа). Поэтому, если вы знаете, что количество меньших элементов в обоих массивах меньше N, вам следует заглянуть в верхнюю половину первого массива, в противном случае вам следует перейти к нижней половине. Таким образом, вы получите общий двоичный поиск с внутренним двоичным поиском. Общая сложность будет O ((logn) ^ 2)
Примечание: если вы не найдете медиану в первом массиве, начните первоначальный поиск во втором массиве. Это не повлияет на сложность