設X[1...n]和Y[1...n]為兩個數(shù)組，每個都包含n個已排序好的數(shù)。給出一個求數(shù)組X和Y中所有2n個元素的中位數(shù)的、O(lgn)時間的算法。

算法思想：

該算法類似于二分查找算法

1.兩個數(shù)組中小于median的個數(shù)為(n - 1)個，假設該median為數(shù)組a中的第k個，k為數(shù)組下標，那么在數(shù)組a中已經(jīng)存在k個值小于median，那么在數(shù)組b中必然有(n - 1) - k = (n-k-1)個數(shù)小于median，如果b[n - k - 2] <= median <= b[n - k - 1]，那么median就找到了，如果median >= b[n - k - 1]，則搜索數(shù)組a中[0，k + 1 ]中的元素，如果median <= b[n?- k - 2]，則搜索數(shù)組a中[k+1,n-1]中的元素.

2.依次類推，類似二分查找，不斷重新設置low，high，middle

3.如果在數(shù)組a中沒找到，則在數(shù)組b中找

詳細代碼

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的类似二分查找算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。