回 帖 发 新 帖 刷新版面

主题:在2个有序数组用二分查找处中值?

在多个有序数组中如何利用二分查找较快地找出一个有条件的未确定值? 
如:在2个有序数组X[n]和Y[n]中,要找出2个数组2n个元素的中值(虽然有2个值,可以只取一个) 

如果先归并排序,再取中间值,则没利用到二分查找 
如何对2个数组同时用二分查找
以下初步想法,请大家修改指正,给出更完整的算法 
int l1=0,r1=n-1,l2=0,r2=n-1; 
int t; 
while(l1 <=r1&&l2 <=r2) 

  int m1=(l1+r1)/2; 
  if(x[m1]>=y[m2-1]&&x[m1] <=y[m2]) return x[m1];//当中值在x[n]中 
  if(y[m2]>=y[m1-1]&&y[m2] <=x[m1]) return y[m2];//当中值在y[n]中 
  if(x[m1] <y[m2-1]) l1=m1+1,r2=m2-1; 
  if(x[m1]>y[m2])  r1=m1-1,l2=m2+1; 


觉得在分支判断时还有遗漏,或会出现矛盾

回复列表 (共1个回复)

沙发

既然要找的中值一定是2n个元素的第n个 
那么在每次查找比较中 
在x[n]中用二分查找x[i],就对应y[n-1-i] 
要找的元素要么是x[i],要么是y[n-1-i] 
不成立则继续二分查找,找到的一定是第n个元素 

这是修改后的算法
int l1=0,r1=n-1; 
while(l1 <=r1) 

  int m1=(l1+r1)/2; 
  int m2=n-1-m1; 
  if(x[m1]>=y[m2-1]&&x[m1] <=y[m2]) return x[m1];//当中值在x[n]中 
  if(y[m2]>=y[m1-1]&&y[m2] <=x[m1]) return y[m2];//当中值在y[n]中 
  if(x[m1] <y[m2-1]) l1=m1+1; 
  if(x[m1]>y[m2])  r1=m1-1; 

请给出更准确的算法设计 谢谢!

我来回复

您尚未登录,请登录后再回复。点此登录或注册