题目：两个有序数组A和B，大小都是n，寻找这两个数组合并后的中位数。时间复杂度为O(logn)。中位数：如果数组有个数是奇数，那么中数的值就是有序时处于中间的数；如果数组个数是偶数的，那么就是有序时中间两个数的平均值。方法一：合并时计数使用MergeSort时的Merge操作，比较两个数组时候计数，当计数达到n时，就可以得到中位数，在归并的数组中，中位数为下标n-1和n的两个数的平均值。时间复杂度O(n)。[cpp]HYPERLINK"http://blog.csdn.net/luxiaoxun/article/details/7960353"\o"viewplain"viewplainHYPERLINK"http://blog.csdn.net/luxiaoxun/article/details/7960353"\o"copy"copyHYPERLINK"http://blog.csdn.net/luxiaoxun/article/details/7960353"\o"print"printHYPERLINK"http://blog.csdn.net/luxiaoxun/article/details/7960353"\o"?"?#include<stdio.h>/*Thisfunctionreturnsmedianofar1[]andar2[].Assumptionsinthisfunction:Bothar1[]andar2[]aresortedarraysBothhavenelements*/intgetMedian(intar1[],intar2[],intn){inti=0;/*Currentindexofi/parrayar1[]*/intj=0;/*Currentindexofi/parrayar2[]*/intcount;intm1=-1,m2=-1;/*Sincethereare2nelements,medianwillbeaverageofelementsatindexn-1andninthearrayobtainedaftermergingar1andar2*/for(count=0;count<=n;count++){/*Belowistohandlecasewhereallelementsofar1[]aresmallerthansmallest(orfirst)elementofar2[]*/if(i==n){m1=m2;m2=ar2[0];break;}/*Belowistohandlecasewhereallelementsofar2[]aresmallerthansmallest(orfirst)elementofar1[]*/elseif(j==n){m1=m2;m2=ar1[0];break;}if(ar1[i]<ar2[j]){m1=m2;/*Storetheprevmedian*/m2=ar1[i];i++;}else{m1=m2;/*Storetheprevmedian*/m2=ar2[j];j++;}}return(m1+m2)/2;}/*Driverprogramtotestabovefunction*/intmain(){intar1[]={1,12,15,26,38};intar2[]={2,13,17,30,45};intn1=sizeof(ar1)/sizeof(ar1[0]);intn2=sizeof(ar2)/sizeof(ar2[0]);if(n1==n2)printf("Medianis%d",getMedian(ar1,ar2,n1));elseprintf("Doesn'tworkforarraysofunequalsize");return0;}方法二：比较两个数组的中位数ar1[]和ar2[]为输入的数组算法过程：1.得到数组ar1和ar2的中位数m1和m22.如果m1==m2，则完成，返回m1或者m23.如果m1>m2，则中位数在下面两个子数组中a)Fromfirstelementofar1tom1(ar1[0...|_n/2_|])b)Fromm2tolastelementofar2(ar2[|_n/2_|...n-1])4.如果m1<m2，则中位数在下面两个子数组中a)Fromm1tolastelementofar1(ar1[|_n/2_|...n-1])b)Fromfirstelementofar2tom2(ar2[0...|_n/2_|])5.重复上面的过程，直到两个子数组的大小都变成26