给定两个有序的整数序列。求中位数，要求复杂度为对数级别。

通常的思路，我们二分搜索中位数，对某个序列里的某个数 我们可以在对数时间内通过二分算法求得两个序列中比它小的数，整体复杂度也是对数级别。但是代码实现较为困难。

换一个思路，我们把中位数不要当作一个数，而当作一个序列的划分。划分后，序列的左半部设为L，右半部设为R 满足max(L)<=min(R)且满足len(L)==len(R)

二分搜索这个划分即可。对于A+B的长度为奇数的情况，我们进行特殊处理，在划分时允许“借一位”。

其中一个序列为空则直接输出答案。

 

补充一个算法，对于两个无序的数列求中位数，《算法概论》中给出了线性的解法。通过类似快速排序的划分方法对数列进行划分，预测中位数可能存在的部分。

class Solution {public:    double findMedianSortedArrays(vector
     
      & nums1, vector
      
       & nums2) {        if(nums2.size()==0) 	{ 	 if(nums1.size()%2==0)return (double)(nums1[nums1.size()/2]+nums1[nums1.size()/2-1])/2.0;	 	else return (double)nums1[nums1.size()/2];	} if(nums1.size()==0) 	{ 	 if(nums2.size()%2==0)return (double)(nums2[nums2.size()/2]+nums2[nums2.size()/2-1])/2.0;	 	else return (double)nums2[nums2.size()/2];	} int len=(nums1.size()+nums2.size())/2; bool flag=(nums1.size()+nums2.size())%2==1; if(flag)len++; int l=-1,r=min((int)nums1.size()-1,len-1); while(true) 	{ 	 int i=(l+r)/2,ii; 	 ii=i+1; 	 int j=len-(i+1)-1,jj; 	 jj=j+1; 	 if(j>=(int)nums2.size()){l=i+1;continue;} 	 int l1=-2147483647,l2=-2147483647,r1=2147483647,r2=2147483647; 	 if(i>=0)l1=nums1[i];	 if(j>=0)l2=nums2[j]; 	 if(ii
       
        =l2)r1=min(l1,r1); 	 if(flag&&l2>l1)r2=min(r2,l2); 	 int maxa=max(l1,l2);int minb=min(r1,r2); 	 if(maxa<=minb){return (double)(maxa+minb)/2.0;} 	 if(l1>r2){r=i-1;continue;} 	 	else{l=i+1;continue;}	}            }};