要是效率達到log2n，首先想到的就是二分查找，首先考慮兩個有序數組長度一樣的情況，我們找到了A[n/2] 和 B[n/2]來比較， 如果他們相等，那樣的話，我們的搜索結束了，因為答案已經找到了A[n/2]就肯定是排序後的中位數了。
如果我們發現B[n/2]>A[n/2]，說明這個數字應該在 A[n/2]->A[n]這個序列裡面，或者在B[1]-B[n/4]這裡面。已經成功的把問題變成了在排序完成的數組A[n/2]-A[n]和B[0]-B[n/2]裡面找到合並以後的中位數，顯然遞歸是個不錯的選擇了。
類似的， 如果B[n/2]<A[n/2]呢？顯然就是在A[0]-A[n/2]和B[n/2]-B[n]裡面尋找了。 www.2cto.com
在繼續想， 這個遞歸什麼時候收斂呢？當然一個case就是相等的值出現， 如果不出現等到這個n==1的時候也就結束了
一樣的， 我們還是把這個兩個數組來比較一下，不失一般性，我們假定B數組比A數組長一點。A的長度為n, B的長度為m。比較A[n/2]和B[m/2] 時候。類似的，我們還是分成幾種情況來討論：
① 如果A[n/2] == B[m/2]，那麼很顯然，我們的討論結束了。A[n/2]就已經是中位數，這個和他們各自的長度是奇數或者偶數無關。
② 如果A[n/2]< B[m/2]，那麼，我們可以知道這個中位數肯定不在[A[0],A[n/2])這個區間內，同時也不在[B[m/2],B[m]]這個區間裡面。這個時候，我們不能沖動地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉。我們只需要把[B[m-n/2],B[m]]和[A[0],A[n/2])扔掉就可以了。（如圖所示的紅色線框），這樣我們就把我們的問題成功轉換成了如何在A[n/2]->A[n]這個長度為n/2的數組和B[1]-B[m-n/2]這個長度為m-n/2的數組裡面找中位數了。問題復雜度即可下降了。
③ 只剩下A[n/2] > B[m/2]，和b類似的，我們可以把A[n/2]->A[n]這塊以及B[1]->B[n/2]這塊扔掉了就行,然後繼續遞歸。
摘自 何昊專欄 程序員面試500問
