题目地址：

https://leetcode.com/problems/median-of-two-sorted-arrays/

给定两个升序数组A AA和B BB，求两个数组所有数的中位数。如果一共偶数个，则取最中间的两个数的平均值。

设各自的长度n nn和m mm，那么如果我们解决了对任意给定的k kk找第k kk小的数，这个问题就解决了。所以先考虑如何解决这个更加一般的问题。我们考虑数组A AA和B BB的各自的前k / 2 k/2k/2（以下的除法都是整除）个数。如果A [ k / 2 − 1 ] < B [ k / 2 − 1 ] A[k/2-1]<B[k/2-1]A[k/2−1]<B[k/2−1]，那么我们可以断言A [ 0 ] , . . . , A [ k / 2 − 1 ] A[0],...,A[k/2-1]A[0],...,A[k/2−1]一定都不是答案，因为如果存在j ≤ k / 2 − 1 j\le k/2-1j≤k/2−1使得A [ j ] A[j]A[j]是第k kk小的数，由于A [ k / 2 − 1 ] < B [ k / 2 − 1 ] A[k/2-1]<B[k/2-1]A[k/2−1]<B[k/2−1]，所以比A [ j ] A[j]A[j]还小的数的个数是小于等于j + k / 2 − 1 < k j+k/2-1< kj+k/2−1<k的，这就矛盾了。所以我们就可以将A [ 0 ] , . . . , A [ k / 2 − 1 ] A[0],...,A[k/2-1]A[0],...,A[k/2−1]舍去，直接从A [ k / 2 ] A[k/2]A[k/2]开始，加上B BB的所有数，找第k − k / 2 k-k/2k−k/2小的数。这样就将要找第k kk小的数转变为了要找第k − k / 2 ≤ k / 2 + 1 k-k/2\le k/2+1k−k/2≤k/2+1小的数，而且重复这种操作时，k kk必然会严格下降到1 11，而对于k = 1 k=1k=1答案是显然的。如果A AA的长度是小于k / 2 k/2k/2的，那么就可以直接断定B [ 0 ] , . . . , B [ k / 2 − 1 ] B[0],...,B[k/2-1]B[0],...,B[k/2−1]不可能是答案，可以直接从B [ k / 2 ] B[k/2]B[k/2]开始和A AA全体中寻找答案，剩下的逻辑与上面类似。代码如下：

classSolution{public:doublefindMedianSortedArrays(vector<int>&v1,vector<int>&v2){intn=v1.size()+v2.size();if(n%2)returnfind(v1,0,v2,0,n/2+1);elsereturn(find(v1,0,v2,0,n/2)+find(v1,0,v2,0,n/2+1))/2.0;}intfind(vector<int>&v1,inti,vector<int>&v2,intj,intk){if(v1.size()-i>v2.size()-j)returnfind(v2,j,v1,i,k);if(v1.size()==i)returnv2[j+k-1];if(k==1)returnv1.size()==i?v2[j]:min(v1[i],v2[j]);intk1=min((int)v1.size()-1,i+k/2-1),k2=j+k-(k1-i+1)-1;if(v1[k1]<v2[k2])returnfind(v1,k1+1,v2,j,k-(k1-i+1));elseif(v1[k1]>v2[k2])returnfind(v1,i,v2,k2+1,k-(k2-j+1));elsereturnv1[k1];}};

时间复杂度O ( log ⁡ ( m + n ) ) O(\log (m+n))O(log(m+n))，空间O ( log ⁡ k ) O(\log k)O(logk)（递归栈深度）。

时间复杂度证明：
设A AA和B BB的数字个数和为N NN，则T ( N , k ) = T ( N − k / 2 , k / 2 ) + O ( 1 ) = T ( N − k / 2 − k / 4 , k / 4 ) + O ( 2 ) = . . . = T ( N − k , 1 ) + O ( log ⁡ k ) = O ( log ⁡ k ) = O ( log ⁡ N ) T(N,k)=T(N-k/2,k/2)+O(1)\\=T(N-k/2-k/4,k/4)+O(2)\\=...=T(N-k,1)+O(\log k)=O(\log k)=O(\log N)T(N,k)=T(N−k/2,k/2)+O(1)=T(N−k/2−k/4,k/4)+O(2)=...=T(N−k,1)+O(logk)=O(logk)=O(logN)

极致优化：

classSolution{public:doublefindMedianSortedArrays(span<int>v1,span<int>v2){autofind=[](thisauto&&find,span<int>v1,inti,span<int>v2,intj,intk)->int{intn=v1.size(),m=v2.size();// Compare v1[i + k/2- 1], v2[j + k - (k/2 - 1)]// v1[i, i + 1, ..., i + k/2 - 1]. k/2// v2[j, j + 1, ..., j + k - k/2 - 1]. k-k/2if(n-i>m-j)returnfind(v2,j,v1,i,k);if(i==n)returnv2[j+k-1];if(k==1)returnmin(v1[i],v2[j]);intk1=min(i+k/2-1,n-1);intk2=j+k-(k1-i+1)-1;if(v1[k1]<v2[k2])returnfind(v1,k1+1,v2,j,k-(k1-i+1));elseif(v1[k1]>v2[k2])returnfind(v1,i,v2,k2+1,k-(k2-j+1));elsereturnv1[k1];};intN=v1.size()+v2.size();if(N%2)returnfind(v1,0,v2,0,N/2+1);elsereturn(find(v1,0,v2,0,N/2)+find(v1,0,v2,0,N/2+1))/2.0;}};

时空复杂度不变。