O(n) 方法是合并两个列表，然后平均中间的两个元素。 但还能进一步优化吗？ 该问题是否有 O(log n) 解决方案？
最佳答案
您可以使用嵌套二分搜索在 O(log n)^2 时间内完成此操作。您对中位数、最高元素和最低元素的两个猜测(您可以通过两次比较得到)。然后取中间。然后通过两次二分搜索找到 mid 的索引。这会告诉您估计值是否太高或太低，并迭代外部二分搜索。
关于arrays - 给定两个数组，每个数组包含 n 个已排序元素，是否有 O(log n) 时间算法来查找所有 2n 个元素的中位数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45117371/