题目：leetcode
Median of Two Sorted Arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
注意：当m+n为偶数时，此题的中位数是中间两个数的平均值。
分析：
1、令数组A始终为长度小的那个数。
2、考虑A为空，B不为空的情况。
3、m+n为偶数和奇数的情况要分开讨论。
4、此题有两种思路：一种是求两个有序数组的第k个数，这里k=(m+n)/2. 另一种思路是每次递归都在中位数的前后删除deletenum长度的数字（这个deletenum约等于数组A的长度的一半），直到数组A长度为2（这是递归的终止条件）。这里我使用第二种思路，，特别要注意的是m==1 和 m==2的情况要单独讨论。第二种情况的时间复杂度为O（log(min(m,n))).
class Solution {public:double findMedianSortedArrays(int A[], int m, int B[], int n) {if(m>n)return findMedianSortedArrays(B,n,A,m);if(m==0){if(n==0)throw exception();if(n & 1){return B[(n-1)/2];}else{double m1=B[(n-1)/2],m2=B[(n-1)/2+1];return (m1+m2)/2;}}int total=m+n;if(total & 1)return findMedianSortedArrays_up(A,0,m-1,B,0,n-1);elsereturn ( findMedianSortedArrays_down(A,0,m-1,B,0,n-1)+findMedianSortedArrays_up(A,0,m-1,B,0,n-1) )/2.0;}//比较小的那个数作为中位数double findMedianSortedArrays_up(int A[], int al,int ar, int B[], int bl,int br){int lena=ar-al+1,lenb=br-bl+1;int mida=al+(ar-al)/2,midb=bl+(br-bl)/2;if(lena==1 || lena==2 ){if(lena==1)return one_multiple_up(B,bl,br,A[al]);else{return two_multiple_up(A,al,ar,B,bl,br);}}else{int deletenum=lena&1?lena/2:lena/2-1;if( A[mida]==B[midb]){return A[mida];}else if( A[mida]<B[midb]){return findMedianSortedArrays_up(A,mida,ar,B,bl,br-deletenum);}else{int offset=lena&1?0:1;return findMedianSortedArrays_up(A,al,mida+offset,B,bl+deletenum,br);}}}double one_multiple_up(int num[], int l,int r,int number){int mid=l+(r-l)/2,len=r-l+1;if(num[mid]==number){return num[mid];}else if(num[mid]<number){if(len & 1){return num[mid];}else{return min(number,num[mid+1]);}}else{if(len & 1){if(len==1){return number;}else{return max(number,num[mid-1]);}}else{return num[mid];}}}double two_multiple_up(int A[], int al,int ar, int B[], int bl,int br){int mida=al+(ar-al)/2,midb=bl+(br-bl)/2;int lenb=br-bl+1;if((A[al]==A[ar] && A[al]==B[midb]) || (A[al]<B[midb] && A[ar]>B[midb])){return B[midb];}else if(A[al]==B[midb] || A[ar]==B[midb]){return B[midb];}else if(A[ar]<B[midb]){if(lenb &1){return max(A[ar],B[midb-1]);///////}else{if(lenb==2)return A[ar];else{return max(B[midb-1],A[ar]);}}}else//A[al]>B[midb]{return min(B[midb+1],A[al]);}}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////比较大的那个数作为中位数double findMedianSortedArrays_down(int A[], int al,int ar, int B[], int bl,int br){int lena=ar-al+1,lenb=br-bl+1;int mida=al+(ar-al)/2,midb=bl+(br-bl)/2;if((lena & 1) == 0){mida++;}if((lenb & 1) == 0){midb++;}if(lena==1 || lena==2){if(lena==1)return one_multiple_down(B,bl,br,A[al]);else{return two_multiple_down(A,al,ar,B,bl,br);}}else{int deletenum=lena&1?lena/2:lena/2-1;if( A[mida]==B[midb]){return A[mida];}else if( A[mida]<B[midb]){int offset=lena&1?0:1;return findMedianSortedArrays_down(A,mida-offset,ar,B,bl,br-deletenum);}else{//int offset=lena&1?0:1;return findMedianSortedArrays_down(A,al,mida,B,bl+deletenum,br);}}}double one_multiple_down(int num[], int l,int r,int number){int mid=l+(r-l)/2,len=r-l+1;if((len & 1) == 0){mid++;}if(num[mid]==number){return num[mid];}else if(num[mid]<number){if(len & 1){if(len==1){return number;}else{return min(number,num[mid+1]);}}else{return num[mid];}}else{if(len & 1){return num[mid];}else{return min(number,num[mid-1]);}}}double two_multiple_down(int A[], int al,int ar, int B[], int bl,int br){int lena=ar-al+1,lenb=br-bl+1;int mida=al+(ar-al)/2,midb=bl+(br-bl)/2;if((lena & 1) == 0){mida++;}if((lenb & 1) == 0){midb++;}if((A[al]==A[ar] && A[al]==B[midb]) || (A[al]<B[midb] && A[ar]>B[midb])){return B[midb];}else if(A[ar]<=B[midb]){return max(A[ar],B[midb-1]);}else if(A[al]>=B[midb]){if(lenb &1){return min(B[midb+1],A[al]);}else{if(lenb==2){return A[al];}else{return min(B[midb+1],A[al]);}}}}};
强者能同命运的风暴抗争。
