2、id:n-1]和Y[0:mid]中查找；（2）如果X[mid]>Y[mid]，则两个数组合并后的中位数应该在X[0:mid]和Y[mid:n-1]中查找；（3）如果X[mid]=Y[mid]，则两个数组合并后的中位数就是X[mid]或者Y[mid]另外考虑特殊情况：如果两个数组的长度为1，则无需比较大小，合并后数组的中位数即为两个数组元素的平均值。如果数组的长度为偶数，令mid为数组的中间两个元素的较小元素的位置，此时数组X的中位数为x=(X[mid]+X[mid+1])/2.0，数组Y的中位数为y=
3、(Y[mid]+Y[mid+1])/2.0(这里考虑到中位数不一定为整数)。则存在以下情况：（1）如果xy，则两个数组合并后的中位数应该在X[0:mid]和Y[mid+1:n-1]中查找；（3）如果x=y，则两个数组合并后的中位数就是x或者y.考虑特殊情况：如果两个数组的长度为2，则如果其中一个数组A的元素刚好处于合并后的数组的中间位置，则最终的中位数为这个数组A的数组元素的平均数。否则，则回到数组长度
4、为偶数的一般情况。具体如下：doubleSearch_Median(int*A,intl1,intr1,int*B,intl2,intr2,intn){/*如果两个数组的长度为，则中位数为所有元素的平均数，其中A,B为要查中位数的数组，l1,r1,l2,r2分别为两个数组每次查询的起始位置和终点位置n为两个数组每次查询时的范围（重新查询的数组长度）*/if(n==1){//数组长度为1的情况return(A[l1]+B[l2])/2.0;}if(n==2){//数组长度为2的情况if(A[l1]>B[
5、l1]&&A[r1]B[r2])return(B[l2]+B[r2])/2.0;else;}//这里使用mid1,mid2分别来记录两个数组每次变化后的中间位置intmid1=(r1+l1)/2;intmid2=(r2+l2)/2;//如果数组的长度为偶数，对数组进行查询if(n%2==0){//这里考虑到偶数数组的中位数是中间两个数的平均数doublex=(A[mid1]+A[mid1+
6、1])/2.0;doubley=(B[mid2]+B[mid2+1])/2.0;if(x7、returnSearch_Median(A,mid1,r1,B,l2,mid2,n/2+1);elsereturnSearch_Median(A,l1,mid1,B,mid2,r2,n/2+1);}}这样一来，因为采用的是二分查找的思想，数组又是已经排好序的，因此每次查找两个数组的中位数的时间复杂度为O(1)，比较的代价为O(1)，而查找过程总得需要重复logn次，因此算法的时间复杂度为O(logn)。2有一实数序列a1,a2,…,aN,若iaj,则(ai,aj)构成了一个逆序对，请使用分
8、治方法求整个序列中逆序对个数，并分析算法的时间复杂性。例如：序列（4,3,2）逆序对有（4,3），（4,2），（3,2）共3个解：数据输入：a数组，n（元素个数）采用归并排序思想：将序列看成一个数组假设f(i,j)为i到j的逆序对个数，取一个分割点k，假设s(i,j,k)表示以k为分割点，第一个元素在i到k中，第二个元素在k+1到j中形成的逆序对数。那么可以形成一个递归式：f(i,j)=f(i,k)+f(k+1,j)+s(i,j,k).采用归并排序算法进
