问题：设X[0:n-1]和Y[0:n-1]为两个数组，每个数组中含有n个已排好序的数。试设计一个O(logn)时间的分治算法，找出X和Y的2n个数的中位数
思想：
对于数组X[0:n-1]和Y[0:n-1]先分别找出X和Y的中位数xa和yb。求中位数的算法是这样的，若n是奇数，即数组X和Y中各有奇数个数字，因为X和Y已经排好序了，所以去数组下标为(n-1)/2处的数即为中位数。若n是偶数，则取(n-1)/2向下取整和向上取整这两个位置的数的平均值作为中位数。
两者进行比较，
(1)若xa=yb则xa或者xb即为整个2n个数中的中位数，算法结束。因为:若每个数组中数字的个数是偶数个，则X中小于中位数的有n/2个，大于中位数的有n/2个，同理Y也是如此，所以在整个2n数组中比xa=yb小的共有n个数，比n大的共有n个数，即为中位数。若每个数组中数字的个数是奇数，则X中小于xa的有(n-1)/2个，大于xa的也有(n-1)/2个，同理Y中也是如此，所以对于xa或者是yb则整个2n数组中小于和大于他们的数分别为(n-1)个，取这两个数的平均值(xa+yb)/2=xa=yb即为中位数.
(2) 若xa>yb,则说明整个2n个数的的中位数一定在X数组的前一半和Y数组的后一半中，因为：若中位数在X数组的中位数之后，则比它小的数共有X数组中大于n/2个数以及Y数组中大于n/2个数总计超过了n个数，不符合中位数的定义。若中位数是在Y数组的前一半之中，则比它大的数字共有Y中包括中位数在内的后半部数加上X数组包括中位数在内的后半部，这样也超过了n个数，不符合中位数的定义。
(3) 若xa<yb,则同上理由，整个2n的数的中位数应该在X数组的后一半和Y数组的前一半中。
确定中位数所在的数组范围后，递归调用求中位数算法对这个范围的数组求中位数重复上述过程，直至：
1.出现xa=yb情况，找到了中位数算法结束。
2.数组分割至左右两部数组只有一个数字的情况，求其平均值即为中位数
代码：
/*
思路：求两有序数组x和y的第k个数，思路如下：
若k为1，则返回两数组的最小值
取x的第i个数x0，取y的第(k-i)个数y0
若x0=y0，则x0即为所求
若x0<y0，则丢弃x的前i个数，k=k-i，递归
若x0>y0，则丢弃y的前(k-i)个数，k=i，递归
*/
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList; public class Solution{ public int findOneSideMedian(int a[]){
int mid;
int length=a.length;
//if(a[])数组长度a.length
if((length&0x01)==0){//判断子数组的长度是奇数还是偶数
mid=(a[length/2]+a[length/2-1])/2;
}else{
mid=a[length/2];
}
return mid;
} public double findMedian(int x[],int y[] int n){
if(n==0){
break;
}
int mid_x=findOneSideMedian(x);
int mid_y=findOneSideMedian(y);
if(n==1){
return (mid_x+mid_y)/2;
}
if(mid_x==mid_y){
return mid_x;
}else if(mid_x>mid_y){
int[] x2=Arrays.copyOfRange(x,0,n/2);
int[] y2=Arrays.copyOfRange(y,Math.ceil(n/2),n);
n=n/2;
findMedian(x2,y2,n);
}else if(mid_x<mid_y){
int[] x2=Arrays.copyOfRange(x,Math.ceil(n/2),n);
int[] y2=Arrays.copyOfRange(y,0,n/2);
n=n/2;
findMedian(x2,y2,n);
}
}
}