algorithm - 我们能证明提取中位数的算法必须对集合进行分区吗？

Question

提取 51 个元素的中值，包括将 51 拆分为 25 的 H(ead) 组，然后是中值，然后是 25 的 T(ail)。我知道的所有算法都以H 和 T 的附加属性使得 [min(H), max(H)[ 和 ]min(T), max(T)] 不重叠。

这个附加属性是否被证明是强制性的（我想是的）？我在哪里可以找到证据（我想它已经完成了很长时间）？

（这只是为了热爱算法）

Answer 1

如果元素不是唯一的，那么这两个集合实际上可以重叠（想象一个包含 51 个相同元素的列表......）

如果元素是唯一的，那么不重叠的性质很容易通过反证来证明。从独特元素的划分中，我们有：

• x < H 中所有 x 的中值
• y > H 中所有 y 的中值

假设 H 和 T 确实重叠。然后我们有：

• x >= y 对于某些 x=max(H), y=min(T)

但这意味着：

• x >= y > 中位数

这是一个矛盾，因为我们已经知道 x < 中位数。因此这两组不能重叠。