從兩個不同長度的排序數組中找到中位數

Question

從兩個給定的排序數組中找出中位數的問題相當已知並且容易（在此之前多次詢問）。 （這可以通過一個簡單的遞歸算法來進行）

我的問題是如何找到位數時，兩個數組有效長度相同的不（即不能同時與歸併排序他們，並找到中位數）

另外，如何找到k排序的相同長度？有沒有一種高效的算法？

我試着回答最後一個問題，但沒有找到一個好的解決方案， 謝謝！

Answer 1

如果您從其中一個數組中選擇一個值並在另一個數組中進行二進制搜索，那麼您將知道每個數組中有多少個值高於和低於所選值，這足以告訴您如何兩者的組合中的許多值高於和低於所選值。

所以你可以在第一個數組上做一個二進制斬波並找出它的哪個值最接近整體中值，然後你可以在第二個數組上做一個二進制斬波並找出它的哪個值最接近整體中位數，並且這兩個數組中的一個必須包含總體中位數。 O（log^2（n））在最壞的情況下，這個代價是兩個外部的二叉印，其中每個猜測花費你一個內部的二叉印，所以O（log^2（n））。

有一對夫婦的想法可能給至少一個實際加速了這一點：

1）在做內部的二進制印章，你不一定要找到完全匹配。只要您減少了匹配足夠的值的時間間隔，以確定所選值是高於還是低於目標中值，就可以返回該範圍內的任何值。

2）您可以查看先前調用內部二進制排列返回的間隔是否是當前調用的可行起點。如果它沒有包含搜索到的值，那麼可能在一側或另一側有相同大小的間隔。