前言
困難 ○ 這題搞了3天實在太難了，本質就是每次排除k/2個數，直到找到第k個數。
題目
給定兩個大小分別為?m?和?n?的正序（從小到大）數組?nums1?和?nums2。請你找出并返回這兩個正序數組的?中位數?。
算法的時間復雜度應該為?O(log (m+n))?。
示例 1：
輸入：nums1 = [1,3], nums2 = [2] 輸出：2.00000 解釋：合并數組 = [1,2,3] ，中位數 2
示例 2：
輸入：nums1 = [1,2], nums2 = [3,4] 輸出：2.50000 解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
思路
筆者一開始的思路是比較兩個數組的中點排除一半數組，直到有一邊只剩一個數，這樣做的缺點在于判斷條件過多，到最后還要判斷奇偶數，非常麻煩。
官方題解
給定兩個有序數組，要求找到兩個有序數組的中位數，最直觀的思路有以下兩種：
使用歸并的方式，合并兩個有序數組，得到一個大的有序數組。大的有序數組的中間位置的元素，即為中位數。
不需要合并兩個有序數組，只要找到中位數的位置即可。由于兩個數組的長度已知，因此中位數對應的兩個數組的下標之和也是已知的。維護兩個指針，初始時分別指向兩個數組的下標 0 的位置，每次將指向較小值的指針后移一位（如果一個指針已經到達數組末尾，則只需要移動另一個數組的指針），直到到達中位數的位置。
假設兩個有序數組的長度分別為 m 和 n，上述兩種思路的復雜度如何？
第一種思路的時間復雜度是 O(m+n)，空間復雜度是 O(m+n)。第二種思路雖然可以將空間復雜度降到 O(1)，但是時間復雜度仍是 O(m+n)。
如何把時間復雜度降低到 O(log(m+n)) 呢？如果對時間復雜度的要求有 log，通常都需要用到二分查找，這道題也可以通過二分查找實現。
根據中位數的定義，當 m+n 是奇數時，中位數是兩個有序數組中的第 (m+n)/2 個元素，當 m+n 是偶數時，中位數是兩個有序數組中的第 (m+n)/2 個元素和第 (m+n)/2+1 個元素的平均值。因此，這道題可以轉化成尋找兩個有序數組中的第 k 小的數，其中 k 為 (m+n)/2 或 (m+n)/2+1。
假設兩個有序數組分別是 A 和 B。要找到第 k 個元素，我們可以比較 A[k/2?1] 和 B[k/2?1]，其中 / 表示整數除法。由于 A[k/2?1] 和 B[k/2?1] 的前面分別有 A[0..k/2?2] 和 B[0..k/2?2]，即 k/2?1 個元素，對于 A[k/2?1] 和 B[k/2?1] 中的較小值，最多只會有 (k/2?1)+(k/2?1)≤k?2 個元素比它小，那么它就不能是第 k 小的數了。
因此我們可以歸納出三種情況：
如果 A[k/2?1]<B[k/2?1]，則比 A[k/2?1] 小的數最多只有 A 的前 k/2?1 個數和 B 的前 k/2?1 個數，即比 A[k/2?1] 小的數最多只有 k?2 個，因此 A[k/2?1] 不可能是第 k 個數，A[0] 到 A[k/2?1] 也都不可能是第 k 個數，可以全部排除。
如果 A[k/2?1]>B[k/2?1]，則可以排除 B[0] 到 B[k/2?1]。
如果 A[k/2?1]=B[k/2?1]，則可以歸入第一種情況處理。
可以看到，比較 A[k/2?1] 和 B[k/2?1] 之后，可以排除 k/2 個不可能是第 k 小的數，查找范圍縮小了一半。同時，我們將在排除后的新數組上繼續進行二分查找，并且根據我們排除數的個數，減少 k 的值，這是因為我們排除的數都不大于第 k 小的數。
有以下三種情況需要特殊處理：
如果 A[k/2?1] 或者 B[k/2?1] 越界，那么我們可以選取對應數組中的最后一個元素。在這種情況下，我們必須根據排除數的個數減少 k 的值，而不能直接將 k 減去 k/2。
如果一個數組為空，說明該數組中的所有元素都被排除，我們可以直接返回另一個數組中第 k 小的元素。
如果 k=1，我們只要返回兩個數組首元素的最小值即可。
class Solution {
public:double findk(vector<int>& nums1, vector<int>& nums2, int k){double ans;int m = nums1.size();int n = nums2.size();int index1 = 0, index2 = 0; //區間起點while(true){//一個數組已完全排除if (index1 == m)return nums2[index2 + k - 1];if (index2 == n)return nums1[index1 + k - 1];//剩余一個要排除，排除大的返回小的if (k == 1)return min(nums1[index1], nums2[index2]);//區間終點，k/2-1是區間長度，如果該長度超過數組長度，直接取數組最后一個值int newindex1 = min(index1 + k / 2 - 1, m - 1);int newindex2 = min(index2 + k / 2 - 1, n - 1);//區間終點值，也就是要比較的值int point1 = nums1[newindex1];int point2 = nums2[newindex2];//終點值小的一邊包括終點全被排除//更新k，更新小的一邊的起點坐標（上一個終點的下一位）//等號在哪里不影響結果if (point1 <= point2){k -= newindex1 - index1 + 1;index1 = newindex1 + 1;}else{k -= newindex2 - index2 + 1;index2 = newindex2 + 1;}}return ans;}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size();int n = nums2.size();double ans;if ((m+n)%2 == 0){ans = (findk(nums1, nums2, (m+n)/2)+findk(nums1, nums2, (m+n)/2+1))/2;}else{ans = findk(nums1, nums2, (m+n)/2+1);}return ans;}
};心得
結束二分專題，這個題目需要非常強的邏輯思維，否則很容易被繞進去。再回顧下解法：奇數找中間數，偶數找中間兩個數除2。定義一個函數找兩個數組的第k位數，定義初始起點為0，數組長度為k/2-1(保證每次排除不會把k排走)，進入循環后計算數組終點：起點+長度，如果超過整個數組長度則取最后一位。比較兩個區間終點，把小的一邊排除，循環比較。直到一邊被完全排除，直接返回另一個數組的index+k個數；或者k==1，還剩一個數要排除，排除大的，返回小的。做這個專題的時候太過急躁了，過于低估，很多題目沒有好好想清楚邊界情況就框框做，這個是個壞習慣。靜下心來，筆算每個題的思路，具體到抽象再到具體，嚴謹嚴謹再嚴謹！
