Q

給定兩個陣列，每個陣列包含n排序的元素，是有O（log n）的-time算法找到所有2n個元素的中值？

2017-07-15 82 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，它幫助 –

相關問題