給定兩個大小分別為?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

給定兩個有序數組，要求找到兩個有序數組的中位數，最直觀的思路有以下兩種：

使用歸并的方式，合并兩個有序數組，得到一個大的有序數組。大的有序數組的中間位置的元素，即為中位數。

不需要合并兩個有序數組，只要找到中位數的位置即可。由于兩個數組的長度已知，因此中位數對應的兩個數組的下標之和也是已知的。維護兩個指針，初始時分別指向兩個數組的下標 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，我們只要返回兩個數組首元素的最小值即可。

用一個例子說明上述算法。假設兩個有序數組如下：

A: 1 3 4 9
B: 1 2 3 4 5 6 7 8 9
兩個有序數組的長度分別是 4 和 9，長度之和是 13，中位數是兩個有序數組中的第 7 個元素，因此需要找到第 k=7 個元素。

比較兩個有序數組中下標為 k/2?1=2 的數，即 A[2] 和 B[2]，如下面所示：

A: 1 3 4 9
↑
B: 1 2 3 4 5 6 7 8 9
↑
由于 A[2]>B[2]，因此排除 B[0] 到 B[2]，即數組 B 的下標偏移（offset）變為 3，同時更新 k 的值：k=k?k/2=4。

下一步尋找，比較兩個有序數組中下標為 k/2?1=1 的數，即 A[1] 和 B[4]，如下面所示，其中方括號部分表示已經被排除的數。

A: 1 3 4 9
↑
B: [1 2 3] 4 5 6 7 8 9
↑
由于 A[1]<B[4]，因此排除 A[0] 到 A[1]，即數組 A 的下標偏移變為 2，同時更新 k 的值：k=k?k/2=2。

下一步尋找，比較兩個有序數組中下標為 k/2?1=0 的數，即比較 A[2] 和 B[3]，如下面所示，其中方括號部分表示已經被排除的數。

A: [1 3] 4 9
↑
B: [1 2 3] 4 5 6 7 8 9
↑
由于 A[2]=B[3]，根據之前的規則，排除 A 中的元素，因此排除 A[2]，即數組 A 的下標偏移變為 3，同時更新 k 的值： k=k?k/2=1。

由于 k 的值變成 1，因此比較兩個有序數組中的未排除下標范圍內的第一個數，其中較小的數即為第 k 個數，由于 A[3]>B[3]，因此第 k 個數是 B[3]=4。

A: [1 3 4] 9
↑
B: [1 2 3] 4 5 6 7 8 9
↑

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {if (nums1.size() > nums2.size()) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.size();int n = nums2.size();int left = 0, right = m;// median1：前一部分的最大值// median2：后一部分的最小值int median1 = 0, median2 = 0;while (left <= right) {// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]int i = (left + right) / 2;int j = (m + n + 1) / 2 - i;// nums_im1, nums_i, nums_jm1, nums_j 分別表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);int nums_i = (i == m ? INT_MAX : nums1[i]);int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);int nums_j = (j == n ? INT_MAX : nums2[j]);if (nums_im1 <= nums_j) {median1 = max(nums_im1, nums_jm1);median2 = min(nums_i, nums_j);left = i + 1;} else {right = i - 1;}}return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;}
};