给定两个数组，每个数组包含 n 个已排序元素，是否存在 O(log n) 时间算法来查找所有 2n 个元素的中位数？
Given two arrays each containing n sorted elements, is there a O(log n)-time algorithm to find the medians of all 2n elements?
O(n)的方法是合并两个列表，然后对中间的两个元素进行平均。
但是它可以进一步优化吗？ 是否有 O(log n) 的解决方案？
您可以使用嵌套二分查找在 O(log n)^2 时间内完成。您对中位数和最高元素以及最低元素的两次猜测（您可以通过两次比较获得）。然后走中路。然后通过两次二进制搜索找到中间的索引。那告诉你你的估计是太高还是太低，并迭代外部二进制搜索。
O(n)的方法是合并两个列表，然后对中间的两个元素进行平均。 但是它可以进一步优化吗？ 是否有 O(log n) 的解决方案？
您可以使用嵌套二分查找在 O(log n)^2 时间内完成。您对中位数和最高元素以及最低元素的两次猜测（您可以通过两次比较获得）。然后走中路。然后通过两次二进制搜索找到中间的索引。那告诉你你的估计是太高还是太低，并迭代外部二进制搜索。