主题:在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;
}
觉得在分支判断时还有遗漏,或会出现矛盾
如:在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;
}
觉得在分支判断时还有遗漏,或会出现矛盾