求 5 个数的中位数

February 04, 2019

55 个数(aa, bb, cc, dd, ee)的中位数,需要进行多少次比较?

“运气”最好的情况下进行 44 次就能确定,比如:

aba\leq baca \leq cdad\leq aeae\leq a

aa 大和比 aa 小的数一样多,aa 的值就是中位数。

通用的算法进行多少次能够找出中位数?

55 个数从小到大排列:

123451 - 2 - 3 - 4 - 5

选取其中 44 个,至少包含 1122,并且这 44 个数中最小的必然是其中之一。

依靠如上规律,我们选取两对数,分别得到序:

aba \leq bcdc \leq d

再比较两对中较小的 aacc,设 aca \leq c 可知 aa 是最小(可能是上面的 11 或者 22)。

剩下的 eebb 组成一对,比较得到序,设 ebe\leq b

现在有两对分别有序的数(ebe - bcdc - d)。要排除其中最小的,只需比较两对中较小的 eecc,设 ece \leq c

排除了 ee,现在剩下三个数,最小的即是中位数,比较 bbcc 即得。

如上方法,66 次比较可得到中位数。

那么:

  1. 如何证明如上方法最优?即不存在通用的 55 次求出的算法?

  2. nn 个无序数至多通过多少次比较得出中位数?