设X[n]和Y[n]为已经排好序的数组,设计一个O(lgn) 时间的算法,

找出X和Y的2n 个数的中位数~~~

大家 帮帮忙啊~~

楼上的 说清楚 点好吗???

我想了好久了的, 大概是不是用折中 查找啊~??

但是排好 序的话,就超过了 时间复杂度了把~~

呵呵`~ 好的啊~~

我今天 上的太长的网了, 我也要先下了~

想好了 一定要告诉我啊~~~~ 而且一定 要想出来啊~~~

太谢谢了~~~~~~~~~~~~~

楼上的想出来没？？？

没这么简单的啊～～

合并的话 就超过了 时间复杂度了～～

呵呵～～ 是啊～～

就是 这个O（lgn） 想的我头疼了～

好了~~

自己 已经 完成了, 谢谢大家的 帮忙~

打不开~~

算法是这样的

int F(int i)

{

if(x[i-1]>=y[n-i]&&x[i]<=y[n-i+1] ) ----------n 为 数组的个数(记住)

return x[i-1];

else

{

if(x[i-1]<y[n-i]&&x[i]<=y[n-i+1])

return F(n/2+i/2);

if(x[i-1]>y[n-i+1]&&x[i]>=y[n-i])

return F(i/2);

else{

if(x[i-1]>=y[n-i]&&x[i]<=y[n-i+1] ) ----------n 为 数组的个数(记住)

return x[i-1];

else

{

if(y[i-1]<x[n-i]&&y[i]<=x[n-i+1])

return F(n/2+i/2);

if(y[i-1]>x[n-i+1]&&y[i]>=x[n-i])

return F(i/2);

}

}

}