已知两个同规模的已序数组,求其中位数
问题：
现在有两个已经排好序的数组，要写一个算法求其中位数，要求算法的时间复杂度是O(n)，空间复杂度是O(1)，其中数组的长度是n.
解法：
显然的，如果有我们设这两个数组是A[0......n-1],B[0......n-1]，则我们比较A[(n-1)/2]与B[(n-1)/2]大小，如果前者大于后者，说明我们要找的中位数在A[0......(n-1)/2]和B[n/2,......n-1]之间；否则，说明我们要找的中位数在A[n/2......n-1]和B[0......(n-1)/2]之间，而这两个数组的元素个数又相同，对此可以递归处理。
//在此函数中,arrayA和arrayB是两个数组，ibeginA(B)和iendA(B)是数组的边界(取闭区间）int middle(int arrayA[], int ibeginA, int iendA, int arrayB[], int ibeginB, int iendB){ if (ibeginA == iendA) { return arrayA[ibeginA]; } int iMidAPos = (ibeginA + iendA) / 2; int iMidBPos = (ibeginB + iendB) / 2; int iMidAVal = arrayA[iMidAPos]; int iMidBVal = arrayB[iMidBPos]; if (iMidAVal > iMidBVal) { //去掉A的右边和B的左边 return middle(arrayA, ibeginA, iMidAPos-1, arrayB, iendB-(iMidAPos-ibeginA)+ 1, iendB); } else { //去掉A的左边和B的右边 return middle(arrayA, iendA-(iMidBPos-ibeginB)+1, iendA, arrayB, ibeginB, iMidBPos-1); }}
