寻找中间数的算法

DraculaW

两个排序数组
A 1 3 5 6
B  2 4 7 9

求一个算法 找两个的中间数 上面的地结果是4
要求O(lg(n))                    //对不起 刚才打错了

我初步的想法是binarysearch的变种
但是还是不很成熟呵呵

[ 本帖最后由 DraculaW 于 2008-2-1 16:14 编辑 ]

cugb_cat

没太明白，为什么是4？

G00GLE

原帖由 cugb_cat 于 2008-2-1 14:59 发表
没太明白，为什么是4？

也许是题目的约定吧，偶数个元素的话中间数为n/2

emacsnw

Merge一下就行了吧。

DraculaW

merge的话时间可能会久一点 应该会是O(n)了吧 呵呵

emacsnw

原帖由 DraculaW 于 2008-1-31 23:52 发表
merge的话时间可能会久一点 应该会是O(n)了吧 呵呵

你不是说要求O(n)吗？呵呵。

DraculaW

对不起  对不起 打少了 不好意思阿

emacsnw

原帖由 DraculaW 于 2008-2-1 00:14 发表
对不起  对不起 打少了 不好意思阿

类似二分法，假设A和B一样长，因为A，B已经有序，直接找到x = median(A)和y = median(B)，若 x == y，返回 x。不然假设 x < y，则只留下A的后半段和B的前半段，递归，问题规模减半。 T[n] = O(1) + T[n/2]，因此复杂度 O(log(n))。
A和B不一样长做法应该差不多，实际实现的时候还要考虑更多的边界条件等等。

converse

有点意思,做个保留好了.

Solidus

大概其写了个东西,看看有没有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[m1] == a2[m2]) return a1[m1];
                               
                                if(a1[m1] < a2[m2])
                                {
                                                l1 = m1 + 1;
                                                r2 = m2;

                                }else
                                {
                                                r1 = m1;
                                                l2 = m2 + 1;
                                }
                                if(l1 > r1) return a1[m1];
                                if(l2 > r2) return a2[m2];
                }


}