Q

给定两个阵列，每个阵列包含n排序的元素，是有O（log n）的-time算法找到所有2n个元素的中值？

2017-07-15 77 views 2 likes

2

为O（n）的方法是合并两个列表并进行平均中间的两个元素。但它可以进一步优化？ 问题是否存在O（log n）解决方案？给定两个阵列，每个阵列包含n排序的元素，是有O（log n）的-time算法找到所有2n个元素的中值？

2017-07-15 Gaurav Anand

+2

http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ –

+0

谢谢@PeterdeRivaz –

A

回答

2

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

2017-07-15 11:38:57

+0

事实上，它可能是一种解决方案，但不能满足需求。由于中位数必须位于两个中位数之间！可以单独使用二进制搜索（循环）吗？ –

+0

这对加速来说是个好主意。但是你仍然需要在另一个数组中找到任何建议答案的索引，即O（log N）。 –

+0

感谢@MalcolmMclean，它帮助 –

相关问题