二分探索：k 番目の値を検索（2題）
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本（通称：蟻本）の章末で紹介されている練習問題をひたすらといている。
二分探索。k 番目の値を検索する問題である。 10^9 個くらいあるデータの中から検索するときにどうするかって問題。
POJ3579: Median
問題概要
N 個の数 X[1], X[2], ..., X[N] の各数の差 |X[i] - X[j]| ( NC2 通りある)の中央値を求める。
3 <= N <= 100,000
X[i] <= 1,000,000,000
解法
O(m) : 中央値が m 以上である
O(m) の判定があまり時間をかけずにできるなら（具体的には O(N log N) 以下の時間でできるなら）、中央値の検索に二分探索が有効に使える。つまり、O(m) を満たす最小の m が中央値である。
X[i] をソートしておく。A = NC2 とする。
発想としては、項の差が m 以下となるものを数えて、それが中央値の位置( (A - 1) / 2 )以下なら、中央値は m 以上であると判断できる。そこで、各 X[i] に対して、|X[i] - X[j]| <= m ( 0 <= j < i) となる j の個数 cnt[i] を数える。cnt[i] の和が (A - 1) /2 以下なら、中央値は m 以上であると言える。cnt[i] の数え方は O(N) で計算できる。
POJ:3685: Matrix
問題概要
N * N の行列があり、i 行 j 列の要素が、 i * i + 100000 * i + j * j - 100000 * j + i * j で与えられる。この行列の小さい方から M 番目の要素を求める。
1 <= N <= 50000
解法
行列の要素を全列挙してソートするやり方だと時間が足りない。
C(x): M 番目の要素は x 以上である
という判定を行って、 C(x) を満たす最大の x を二分探索で求めれば、それが答え。C(x) の判定方法を考える。C(x) は言い換えると、
「 x より小さい要素の個数が M 未満である」
ということだ。これは O(N log N) で判定可能だろうか。
要素の値を計算する関数を
f(i, j) = i * i + 100000 * i + j * j - 100000 * j + i * j
とする。
f(i, j) は j を固定すると i に関して単調増加であある。
ということは、x よりも小さい要素の個数を数えるには、j に関してループを回しながら、 i に関して二分探索を行えば O(N log N) で判定可能である。
