先看題：

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

算法的時間復雜度應(yīng)該為?O(log (m+n))?。

時間復雜度O(m+n)的解法很好想，依次步進遍歷兩個數(shù)組，每一次哪個數(shù)組的值小就步進哪一個，直到走到中位數(shù)位置。需要注意的點有：

1. 某個數(shù)組已經(jīng)遍歷完了。

2. 在總個數(shù)為偶數(shù)的情況下（即中位數(shù)為中間倆數(shù)平均值），需要記錄最新兩個元素的值，并且在return的時候?qū)nt轉(zhuǎn)換為double。

接下來記錄時間復雜度O(log(m+n))的解法。

很顯然用的應(yīng)該是二分，但要對兩個數(shù)組在不合并的情況下進行二分。

我們先看總元素為偶數(shù)的情況，數(shù)組1有4個元素，數(shù)組2有6個元素，總計10個，應(yīng)該分成左邊5個右邊5個。此時可以發(fā)現(xiàn)，我們需要的兩個中位數(shù)8和9，即為兩個數(shù)組左邊元素的最大值（即數(shù)組1左最大值8和數(shù)組2左最大值6的最大值）和兩個數(shù)組右邊元素的最小值。

當總元素個數(shù)為奇數(shù)的時候，我們采用左邊比右邊多一個的方式（右邊多也行），可以發(fā)現(xiàn)中位數(shù)即為兩個數(shù)組左邊元素的最大值（6和7中的7）。

那么在知道了成功分割之后如何得到答案，接下來的問題就是如何分割。

我們設(shè)數(shù)組1長度為m，數(shù)組2長度為n，那么左邊就應(yīng)該有?(m+n+1)/2 個元素，記為allLeft（注意整型除法向0取整，因此無論m+n的奇偶都用這個公式）。在已知了左邊一共有多少個元素時，確定了數(shù)組1當中左邊有?i?個元素，那么數(shù)組2左邊一定有allleft - i?個元素。

其次，用什么條件來判斷分割線已經(jīng)是正確的了呢？

因為倆數(shù)組本身就是有序的，我們只需要在數(shù)組之間比較就行，即 數(shù)組1的左最大 < 數(shù)組2的右最小，并且 數(shù)組2的左最大 < 數(shù)組1的右最小。在上圖為6<8，?7<15。

那么在二分的過程中只需要上述條件任取一個來縮小范圍即可。如上圖，12<8不成立，因此在數(shù)組1的分割線應(yīng)該右移。

在分割完成后取出上述提及的分割線左右總計4個元素再根據(jù)奇偶進行計算返回即可。

細節(jié)：

1. 在二分的時候需要注意是否會進入死循環(huán)

2. 無論是選取數(shù)組左邊最大值作為i，j還是右邊最小值作為i，j，在對應(yīng)+1-1操作的時候都需要考慮是否存在下標越界的情況。需要控制right和left的取值和中間位置計算方法來避免越界。

3. 在分割完成后，在取分割線左右值的時候需要注意越界問題（存在某個數(shù)組全在左邊或者全在右邊的情況）。

部分代碼（留檔）：

包括 二分，取左右值，返回 部分。

????????int left = 0;

? ? ? ? int right = m;

? ? ? ? while (left < right){

? ? ? ? ? ? int i = left + (right - left + 1) / 2; ? //+1防止當left=i時進入死循環(huán)

? ? ? ? ? ? int j = allLeft - i;

? ? ? ? ? ? //計算出nums1數(shù)組左邊的數(shù)量i即可得知nums2數(shù)組的j；i和j分別為倆數(shù)組分割線后第一個元素（右邊最小值）

? ? ? ? ? ? if (nums1[i-1] < nums2[j]){

? ? ? ? ? ? ? ? //如果數(shù)組1的左最大 小于 數(shù)組2的右最小，說明分割線在數(shù)組1的位置還能右移

? ? ? ? ? ? ? ? left = i;

? ? ? ? ? ? }

? ? ? ? ? ? else{

? ? ? ? ? ? ? ? right = i-1;

? ? ? ? ? ? } ? ? ?

? ? ? ? }

? ? ? ? int i = left;

? ? ? ? int j = allLeft - i;

? ? ? ? int nums1LeftMax = i == 0 ? INT_MIN : nums1[i-1]; ? //防止越界

? ? ? ? int nums1RightMin = i == m ? INT_MAX : nums1[i];

? ? ? ? int nums2LeftMax = j == 0 ? INT_MIN : nums2[j-1];

? ? ? ? int nums2RightMin = j == n ? INT_MAX : nums2[j];

? ? ? ? if ((m+n) % 2 == 1 ){

? ? ? ? ? ? return max(nums1LeftMax, nums2LeftMax);

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? return (double)(max(nums1LeftMax,nums2LeftMax) + min(nums2RightMin, nums1RightMin)) / 2;