深刻的刻画们

· · 算法·理论

约定与记号

  1. 若 a 为一个长度为 n 的数组，记 a_i 为 a 的第 i(1 \leq i \leq n) 个元素的值。

中位数

约定与记号

设此处中位数的研究对象为一个长度为 n 的数组 a，设 b 为 a 从小到大排序后的结果。

定义 \operatorname{Med}(a) 为 a 的中位数，此处规定 a 的中位数为 b_{\lfloor \frac{n+1}{2} \rfloor}。

记 a 中 < x 的数的个数为 c，= x 的个数为 d，> x 的个数为 e。

\operatorname{Med}(a) \leq x 的充要条件

c + d \ge e

x \leq \operatorname{Med}(a) 的充要条件

c < d + e

\operatorname{Med}(a) = x 的充要条件

即 \operatorname{Med}(a) \leq x \land x \leq \operatorname{Med}(a)：

c + d \ge e \land c < d + e