寻找中间数的算法

galaxywar

一样长的话, 找第一行的中间数就行了;
如果第一行个数为偶数, 那这行中间数有两个, 取他们俩之间那个, 也就是第二行的位于第一个以下的那个.

zgongjin

收下了

tcs_chen

原帖由 emacsnw 于 2008-2-1 17:45 发表


类似二分法，假设A和B一样长，因为A，B已经有序，直接找到x = median(A)和y = median(B)，若 x == y，返回 x。不然假设 x < y，则只留下A的后半段和B的前半段，递归，问题规模减半。 T[n] = O(1) + T[n/2]， ...

正解
可以结贴了 ：）

jigloo

这类火星问题建议先搜索一下csdn

cjaizss

原帖由 jigloo 于 2008-2-11 19:58 发表
这类火星问题建议先搜索一下csdn

这是算法级的讨论，不关csdn啥事

jigloo

呃？我隐约感到犯了忌讳。

BenBear

std::nth_element() 挺好的……

sunnyfun

北京大学2006年计算机软件基础考研试题
主要思想确实是折半查找，比较两个数列的中位数，比较大小，而后，据此截出两个数组的各一半，再进行递归。
网上搜到的，呵呵。

tyc611

算法导论第二版，习题9.3-8

tyz

怎么感觉和大学学算法时候第一个实验一样呢