寻找中间数的算法
两个排序数组A 1 3 5 6
B2 4 7 9
求一个算法 找两个的中间数 上面的地结果是4
要求O(lg(n)) //对不起 刚才打错了
我初步的想法是binarysearch的变种
但是还是不很成熟呵呵
[ 本帖最后由 DraculaW 于 2008-2-1 16:14 编辑 ] 没太明白，为什么是4？ 原帖由 cugb_cat 于 2008-2-1 14:59 发表 http://bbs.chinaunix.net/images/common/back.gif
没太明白，为什么是4？
也许是题目的约定吧，偶数个元素的话中间数为n/2 Merge一下就行了吧。 merge的话时间可能会久一点 应该会是O(n)了吧 呵呵 原帖由 DraculaW 于 2008-1-31 23:52 发表 http://bbs.chinaunix.net/images/common/back.gif
merge的话时间可能会久一点 应该会是O(n)了吧 呵呵
你不是说要求O(n)吗？呵呵。 对不起对不起 打少了 不好意思阿 原帖由 DraculaW 于 2008-2-1 00:14 发表 http://bbs.chinaunix.net/images/common/back.gif
对不起对不起 打少了 不好意思阿
类似二分法，假设A和B一样长，因为A，B已经有序，直接找到x = median(A)和y = median(B)，若 x == y，返回 x。不然假设 x < y，则只留下A的后半段和B的前半段，递归，问题规模减半。 T = O(1) + T，因此复杂度 O(log(n))。
A和B不一样长做法应该差不多，实际实现的时候还要考虑更多的边界条件等等。 有点意思,做个保留好了. 大概其写了个东西,看看有没有bug,
int search_mid(int *a1, size_t count1, int *a2, size_t count2)
{
size_t l1 = 0, r1 = count1-1;
size_t l2 = 0, r2 = count2-1;
for(;;)
{
size_t m1 = (l1 + r1)/2;
size_t m2 = (l2 + r2)/2;
if(a1 == a2) return a1;
if(a1 < a2)
{
l1 = m1 + 1;
r2 = m2;
}else
{
r1 = m1;
l2 = m2 + 1;
}
if(l1 > r1) return a1;
if(l2 > r2) return a2;
}
}