中央値と二分探索 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

中央値という概念は二分探索と相性がすこぶるいい。ここでその性質を応用した例題を記す。

中央値の二分探索

中央値というのは次の条件を満たす数列の

1.floor(N/2)番目(0-index)

これは「次の二つの条件を満たす」ことと同値である。

1.ある値Xがあり、floor(N/2)個以上の値がX以上
2.そのXになりうる候補の中での最大のものが中央値となる。

この言い換えによって、Xを二分探索することができるようになる。（○○の最大、最小で判断関数があるものは二分探索に応用可能）
典型な問題を紹介する。最も上記のことそのままであるけど。

ARC101-D Medians of Medians(700)-中央値と二分探索

虐殺700の回。しかし問題自体は良問である。この問題は二つの知見にまとめられ、これはそのうちの一つである。
中央値の中央値ということになるが、セオリー通り二分探索で考えてみる。つまり、Xを二分探索条件として、

中央値列のうちXより大きいのがfloor(N/2)個以上あるか。

を使えばよい。これを満たすときはXの下限を引き上げ満たさねば上限を引き下げる。
中央値列の部分をさらに言いかえすると、

[i, j](ここでは閉区間を使用する)の列の中で、Xより大きいのがfloor((j-i+1)/2)個以上あるものの数が、全体でfloor(N/2)個あるかどうか

と同値である。
これを愚直にやると、二分探索でO(log max_n)、Xあたりの判定関数がO(n^2)となり、間に合わない。
しかし、ここでさらにテクニックを駆使して、オーダーを落とせる。詳しくは転倒数への帰着のARC101Dに続きがある。