https://www.cnblogs.com/voidsky/p/5373982.html
問題介紹
這是個超級超級經(jīng)典的分治算法！！這個問題大致是說禀梳，如何在給定的兩個有序數(shù)組里面找其中的中值浓冒，或者變形問題衙吩，如何在2個有序數(shù)組數(shù)組中查找Top K的值（Top K的問題可以轉(zhuǎn)換成求第k個元素的問題）笔刹。這個算法在很多實(shí)際應(yīng)用中都會用到芥备，特別是在當(dāng)前大數(shù)據(jù)的背景下。
我覺得下面的這個思路特別好舌菜，特別容易理解Ｃ瓤恰！請按順序看日月。是來自leetcode上的stellari英文答案袱瓮，我整理并自己修改了一下。
預(yù)備知識
先解釋下“割”
我們通過切一刀爱咬，能夠把有序數(shù)組分成左右兩個部分尺借，切的那一刀就被稱為割(Cut)，割的左右會有兩個元素精拟，分別是左邊最大值和右邊最小值燎斩。
我們定義L = Max(LeftPart)，R = Min(RightPart)
Ps. 割可以割在兩個數(shù)中間蜂绎，也可以割在1個數(shù)上栅表，如果割在一個數(shù)上，那么這個數(shù)即屬于左邊荡碾，也屬于右邊谨读。（后面講單數(shù)組中值問題的時候會說）
比如說[2 3 5 7]這個序列，割就在3和5之間
[2 3 / 5 7]
中值就是（3+5）/2 = 4
如果[2 3 4 5 6]這個序列坛吁，割在4上劳殖，我們可以把4分成2個
[2 3 (4/4) 5 7]
中值就是（4+4）/2 = 4
這樣可以保證不管中值是1個數(shù)還是2個數(shù)都能統(tǒng)一運(yùn)算。
割和第k個元素
對于單數(shù)組拨脉，找其中的第k個元素特別好做哆姻，我們用割的思想就是：
常識1：如果在k的位置割一下，然后A[k]就是L玫膀。換言之矛缨，就是如果左側(cè)有k個元素，A[k]屬于左邊部分的最大值帖旨。（都是明顯的事情箕昭，這個不用解釋吧！）
雙數(shù)組
我們設(shè):
????Ci為第i個數(shù)組的割解阅。
????Li為第i個數(shù)組割后的左元素.
????Ri為第i個數(shù)組割后的右元素落竹。
[圖片上傳失敗...(image-82acc2-1584541055375)]
如何從雙數(shù)組里取出第k個元素
[圖片上傳失敗...(image-9c664f-1584541055375)]
- 首先????<=????Li<=Ri是肯定的（因為數(shù)組有序，左邊肯定小于右邊）
- 如果我們讓??1<=??2L1<=R2 && ??2<=??1L2<=R1
- 那么左半邊 全小于右半邊货抄，如果左邊的元素個數(shù)相加剛好等于k述召，那么第k個元素就是Max(L1,L2)朱转，參考上面常識1。
- 如果 L1>R2积暖，說明數(shù)組1的左邊元素太大（多）藤为，我們把C1減小，把C2增大夺刑。L2>R1同理缅疟，把C1增大，C2減小性誉。
假設(shè)k=3
對于
[1 4 7 9][1 4 7 9]
[2 3 5][2 3 5]
設(shè)C1 = 2窿吩，那么C2 = k-C1 = 1
[1 4/7 9][1 4/7 9]
[2/3 5][2/3 5]
這時候，L1(4)>R2(3)错览，說明C1要減小凌彬，C2要增大弯淘，C1 = 1讼溺，C2=k-C1 = 2
[1/4 7 9][1/4 7 9]
[2 3/5][2 3/5]
這時候寇荧，滿足了??1<=??2L1<=R2 && ??2<=??1L2<=R1，第3個元素就是Max(1,3) = 3羞海。
如果對于上面的例子忌愚，把k改成4就恰好是中值。
下面具體來看特殊情況的中值問題却邓。
雙數(shù)組的奇偶
中值的關(guān)鍵在于硕糊，如何處理奇偶性，單數(shù)組的情況腊徙，我們已經(jīng)討論過了简十，那雙數(shù)組的奇偶問題怎么辦，m+n為奇偶處理方案都不同撬腾。
讓數(shù)組恒為奇數(shù)
有沒有辦法讓兩個數(shù)組長度相加一定為奇數(shù)或偶數(shù)呢螟蝙？
其實(shí)有的，虛擬加入‘#'(這個trick在manacher算法中也有應(yīng)用)民傻，讓數(shù)組長度恒為奇數(shù)（2n+1恒為奇數(shù)）胰默。
Ps.注意是虛擬加，其實(shí)根本沒這一步漓踢，因為通過下面的轉(zhuǎn)換牵署，我們可以保證虛擬加后每個元素跟原來的元素一一對應(yīng)
映射關(guān)系
這有什么好處呢，為什么這么加?因為這么加完之后喧半，每個位置可以通過/2得到原來元素的位置碟刺。
在虛擬數(shù)組里表示“割”
不僅如此，割更容易薯酝，如果割在‘#'上等于割在2個元素之間半沽，割在數(shù)字上等于把數(shù)字劃到2個部分。
奇妙的是不管哪種情況：
Li = (Ci-1)/2
Ri = Ci/2
例：
- 割在4/7之間‘#'吴菠，C = 4者填，L=(4-1)/2=1 ，R=4/2=2
剛好是4和7的原來位置做葵！ - 割在3上占哟，C = 3，L=(3-1)/2=1酿矢，R=3/2 =1榨乎，剛好都是3的位置！
剩下的事情就好辦了瘫筐，把2個數(shù)組看做一個虛擬的數(shù)組A蜜暑，目前有2m+2n+2個元素，割在m+n+1處策肝，所以我們只需找到m+n+1位置的元素和m+n+2位置的元素就行了肛捍。
左邊：A[m+n] = Max(L1+L2)
右邊：A[m+n+1] = Min(R1+R2)
Mid = (A[m+n]+A[m+n+1])/2
= (Max(L1+L2) + Min(R1+R2) )/2
至于在兩個數(shù)組里找割的方案，就是上面的方案之众。
分治的思路
有了上面的知識后拙毫，現(xiàn)在的問題就是如何利用分治的思想。
怎么分棺禾？
最快的分的方案是二分缀蹄，有2個數(shù)組，我們對哪個做二分呢膘婶？
根據(jù)之前的分析缺前，我們知道了，只要C1或C2確定竣付，另外一個也就確定了诡延。這里，為了效率古胆，我們肯定是選長度較短的做二分肆良，假設(shè)為C1。
怎么治逸绎？
也比較簡單惹恃，我們之前分析了：就是比較L1,L2和R1,R2。
- L1>R2棺牧，把C1減小巫糙，C2增大〖粘耍—> C1向左二分
- L2>R1参淹，把C1增大醉锄，C2減小≌阒担—> C1向右二分
越界問題
如果C1或C2已經(jīng)到頭了怎么辦恳不？
這種情況出現(xiàn)在：如果有個數(shù)組完全小于或大于中值】牛可能有4種情況：
- C1 = 0 —— 數(shù)組1整體都比中值大烟勋，L1 >R2，中值在2中
- C2 = 0 —— 數(shù)組1整體都比中值小筐付，L1 <R2卵惦，中值在1中
- C1 = n*2 —— 數(shù)組1整體都比中值小，L1 <R2瓦戚，中位數(shù)在2中
- C2 = m*2 —— 數(shù)組1整體都比中值大沮尿，L1 >R2，中位數(shù)在1中
考慮下面兩種情況了伤极，解決方案：
- 如果C1 = 0 —> 那么我們縮小L1蛹找，L1 = INT_MIN，保證判斷正確哨坪。
- 如果C1 = n*2 —> 那么我們增大R1庸疾，R1 = INT_MAX，保證判斷正確当编。
剩下兩種情況解決方案類似届慈。
