題目：給定兩個(gè)大小分別為?m?和?n?的正序（從小到大）數(shù)組?nums1?和?nums2。請(qǐng)你找出并返回這兩個(gè)正序數(shù)組的?中位數(shù)?。

例子：nums1=[1,2],nums2=[3,4],那么中位數(shù)就是2.5。假如一個(gè)nums為空，那么中位數(shù)就是另外一數(shù)組的中位數(shù)。

答：首先最暴力、直接的解法就是合并數(shù)組，再排序求中位數(shù)。

????????這種解法在Python中實(shí)現(xiàn)比較簡(jiǎn)單，看下代碼塊：

利用數(shù)組的一些方法可以輕松完成算法實(shí)現(xiàn)。在力扣上的計(jì)算速度和內(nèi)存占用都還行。但是在時(shí)間和空間復(fù)雜度上還是有待商榷的（ps：還未學(xué)習(xí)相關(guān)概念）。

接下來(lái)介紹在力扣官方解答中的解答：

一、二分查找法

????????首先要明白的就是上述的暴力解法是遍歷了所有數(shù)字的。而二分查找法的優(yōu)點(diǎn)就是去掉了一些數(shù)組片段，減少了多余的遍歷工作。

????????一般來(lái)講：對(duì)于兩正序數(shù)組A、B分別為m、n項(xiàng)，其合并后的中位數(shù)是第（m+n）/2個(gè)【m+n為奇數(shù)】或第（m+n）/2個(gè)和第（m+n）/2+1個(gè)的平均值【m+n為偶數(shù)】，二分查找法的是令k=（m+n）/2或（m+n）/2+1，再在比較每個(gè)數(shù)組內(nèi)的[k/2-1]項(xiàng)，這樣就有最多2*（k/2-1）項(xiàng)的數(shù)比這兩個(gè)數(shù)組中的[k/2-1]較小的項(xiàng)還小，下面就分情況來(lái)考慮：

• 當(dāng)A[k/2-1]<B[k/2-1]時(shí)：那么可以的到A中的前[k/2-1]項(xiàng)數(shù)是一定在右邊的，不可能是A+B中的中位數(shù)的，因此把A的前[k/2-1]項(xiàng)舍去。

• 當(dāng)A[k/2-1]>B[k/2-1]時(shí)：同理舍去B的前[k/2-1]項(xiàng)。

• 當(dāng)A[k/2-1]=B[k/2-1]時(shí)：這種情況其實(shí)舍去A、B中那個(gè)都無(wú)所謂，因?yàn)锳、B中的前[k/2-1]項(xiàng)都是較小的，不可能是A+B的第k小的數(shù)。

那么這樣就可以減少遍歷片段以來(lái)節(jié)約時(shí)間，每次舍去一部分，舍去的那個(gè)數(shù)組的【0~k/2-1】項(xiàng)不在被遍歷，因此遍歷的數(shù)少了k/2個(gè)，那么k的值更新為k-k/2。那么下一步二分查找的時(shí)候就是更新后的k，比較新的A[k/2-1]和B[k/2-1]的大小，再舍去多余的片段。在這里因?yàn)槿サ袅薻/2個(gè)，k的值逐漸減小，這樣來(lái)二次劃分會(huì)逐漸靠近中位數(shù)。即最開(kāi)始的時(shí)候A+B的第k個(gè)。當(dāng)k=1的時(shí)候，中位數(shù)也就是劃分去掉后的兩新數(shù)組的首項(xiàng)，比較其大小即最小的是第k小的數(shù)。

但是存在特殊情況，即A[k/2-1]和B[k/2-1]超界了，那么這個(gè)時(shí)候，就取對(duì)應(yīng)的數(shù)組最后一個(gè)數(shù)，若是舍去的時(shí)候要舍去這個(gè)小數(shù)組，k值更新的時(shí)候去掉小數(shù)組的個(gè)數(shù)，而不是取掉k/2；A/B若有一個(gè)是空的，那么只需要考慮另外一個(gè)數(shù)組的第k個(gè)就行，那即A+B中第k小的數(shù)。

python代碼如下：

看到官方的這個(gè)解答，佩服把算法代碼化的實(shí)力，自己還需要多努力?。?！這里就不畫(huà)流程圖了，主要解釋下代碼實(shí)現(xiàn)算法的思路：

????????這里是創(chuàng)建了一個(gè)函數(shù)獲取的第k個(gè)數(shù)，函數(shù)的參數(shù)是由兩數(shù)組的程度決定的，可以看到這里判別了數(shù)組的長(zhǎng)度是奇數(shù)還是偶數(shù)，是奇數(shù)就是第k個(gè)數(shù)就是中位數(shù)，偶數(shù)是取中間兩數(shù)的平均值。故會(huì)有上述代碼的主函數(shù)段。k的值確定后，看getKelement（k）是怎么操作的？首先是創(chuàng)建了兩索引index，再判斷特殊情況，首先是兩者空數(shù)組的情況，直接返回另外數(shù)組的第k個(gè)數(shù)；然后判斷k是否更新到1了，是的話返回首項(xiàng)最小值。重點(diǎn)是正常的情況，每個(gè)數(shù)組創(chuàng)建一個(gè)新的索引，新的索引是之前的索引+k//2-1和數(shù)組右邊界的最小值（出界的情況考慮進(jìn)去了），第一步是可以理解的，就是第[k//2-1]項(xiàng),然后比較大小，再根據(jù)情況更新k的值，就是k-k//2，之所以后面加1是數(shù)組索引是從0開(kāi)始的。后面的index賦值也是同樣的道理，因?yàn)閺?~k//2-1都舍去了，就從k//2開(kāi)始了。然后就繼續(xù)二分了，這里我開(kāi)始以為會(huì)重新創(chuàng)建數(shù)組，后來(lái)發(fā)現(xiàn)是我菜了，只是指針的范圍往前走了就行。newindex后面的賦值因?yàn)閺膇ndex開(kāi)始取值了，故需要加上index。

二、劃分?jǐn)?shù)組

????????這里是最np的算法了，首先咱要理解中位數(shù)的定義了。

????????中位數(shù)是將一個(gè)集合劃分為兩個(gè)長(zhǎng)度相等的子集，其中一個(gè)子集中的元素總是大于另一個(gè)子集中的元素。

????????在這里我們要注意關(guān)鍵詞? 長(zhǎng)度相等，一個(gè)子集的元素總是大于或等于另外一個(gè)子集的元素；

????????這是這個(gè)算法的主要邏輯，也就是把A+B劃分為兩個(gè)子集，其中一個(gè)子集的最大值總是小于另外一個(gè)子集的最小值。且兩子集的數(shù)字個(gè)數(shù)相同或 數(shù)值小的子集多一個(gè)數(shù)。? ? ? ??

????????上圖是算法的示意圖，A/B在i/j位置分割，使得左邊的元素個(gè)數(shù)等于右邊的元素個(gè)數(shù)。且滿(mǎn)足下面公式：

????????1式中的主要目的是判別左邊的最大值是否小于或等于右邊的最小值。2式的主要目的是使得左右兩邊的元素個(gè)數(shù)相同。當(dāng)不滿(mǎn)足的時(shí)候，需要調(diào)整i的值，從而j的值也會(huì)改變，那么A/B兩數(shù)組進(jìn)行左右移動(dòng)，一直保持著2式的關(guān)系，即虛線兩側(cè)的元素個(gè)數(shù)相同。其中1式式可以等價(jià)于存在最大的i值，使得：

????????因此遍歷A數(shù)組尋找滿(mǎn)足上述條件的最大i值，因此一般使元素?cái)?shù)目較小的數(shù)組作為A,這樣求解的時(shí)候較快。

????????但是存在情況就是，A數(shù)組的元素過(guò)少，以致i==0，或者i==m了，這個(gè)時(shí)候就是出界了。處理的方法就是當(dāng)i==0的時(shí)候，[i-1]項(xiàng)為-∞。i==m時(shí)，[i]為+∞。這個(gè)處理并不影響上述的邏輯。當(dāng)A數(shù)組為空的時(shí)候，1式條件是永遠(yuǎn)滿(mǎn)足的，就是使得2式條件滿(mǎn)足即可，也就是查找一個(gè)正序數(shù)組的中位數(shù)。

????????下面是我膜拜的代碼：

膜拜的主要點(diǎn)是

• i的值是用二分查找，分別調(diào)整left和right的值

• 始終貫徹著中位數(shù)的概念

• 把特殊情況也得包括進(jìn)去了

記錄學(xué)習(xí)，生生不息~，