arrays - 给定两个数组，每个数组包含 n 个已排序元素，是否存在 O(log n) 时间算法来查找所有 2n 个元素的中位数？

Question

O(n) 方法 是合并两个列表然后平均中间的两个元素。但是它可以进一步优化吗？ 是否有 O(log n) 的解决方案？

Answer 1

您可以使用嵌套二分查找在 O(log n)^2 时间内完成。您对中位数和最高元素以及最低元素的两次猜测(您可以通过两次比较获得)。然后走中路。然后通过两次二进制搜索找到中间的索引。这会告诉您您的估计是太高还是太低，然后迭代外部二分搜索。