Найдите средний элемент в объединенных массивах в O (logn)

У нас есть два сортированных массива того же размера 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). Какие-либо идеи?

8
задан Ben 28 August 2012 в 19:04
поделиться