中央値関連のライブラリに関して

何らかの順序を持った型 T: Ord があって、それに関する何らかの（多重）集合の中央値を求めるライブラリを作りたいとします。

たとえば単に配列 a: [T] の中から中央値を探すだけだったり、a: [T], b: [T] から a[i] + b[j] として考えられるものの中央値 (cf. ARC 037 C) だったり、集合を作るパートは場合によります。

よくある（たとえば中学・高校などで習う）中央値の定義では、

• 要素数 $n$ が奇数のとき、小さい方から（1-indexed で）$(n+1)/2$ 番目の値
  • たとえば $n=3$ なら $(n+1)/2=2$ 番目の値となる
• $n$ が偶数のとき、小さい方から $n/2$ 番目の値と $n/2+1$ 番目の値の平均値
  • たとえば $n=4$ なら $n/2=2$ 番目と $2+1=3$ 番目の値の平均となる

のようになるのがメジャーかと思います。

一方、ライブラリ設計の文脈においては、「T が整数型だったとしてもそれら二つの平均は T で表せるとは限らない」「偶数と奇数で場合分けするのは面倒」「返り値の型を T 以外にするとなると厄介」など諸々不都合が多いです。

ところで、先の定義は $n$ の偶奇によらず、次のように言い換えられます。

• 小さい方から $\ceil{n/2}$ 番目の値と $\ceil{(n+1)/2}$ 番目の値の平均値
  • あるいは、0-indexed で $\floor{(n-1)/2}$ 番目と $\floor{n/2}$ 番目の平均値など
  • あるいは、0-indexed で $\floor{(n-1)/2}$ 番目と $\ceil{(n-1)/2}$ 番目の平均値など

そこで、$n$ の偶奇によらず $\ceil{n/2}$ 番目の値と $\ceil{(n+1)/2}$ 番目の値の pair を返すことにすれば、呼び出し側での計算に任せることができそうです。 返り値の型は (T, T) になります。問題によっては $\ceil{n/2}$ の方だけを要求されたりしますから、そういうときは片方を捨てるだけでよいです。

また、Rust のような言語では、Reverse という wrapper があり、Reverse(T) と書くと逆向きの順序で計算してくれるようになります。そうした型を使いつつ、必要に応じて 2 回呼び出す前提で $\ceil{n/2}$ 番目だけを返すという設計もありだと思います*1。 あるいは、use_ceil: bool のようなフラグを使うような方針もありでしょうか。あまりうれしくない気もしていますがわかりません。

$-\infty$ に相当する値や $+\infty$ に相当する値を追加することで偶奇を適当に合わせるという方針も一瞬考えましたが、変なコーナーケースができがちな気がするのであまりやりたくはないですね。

ところで、空の配列の場合は中央値が存在しませんから、やはり返り値の型は Option<(T, T)> にするべきなのではないでしょうか。という派閥もある気がしており、困りましたね（競プロ文脈ではあまりそういうことはないため）（でもあまりないケースで勝手にバグを踏んで泣くことも多いので、考えておく必要はある）。

人には人のライブラリ設計なので、参考にしたりしなかったりしてください。

*1:計算過程で四則演算などが必要になる場合は面倒かも。