lower_bound F#(Beta)編（paizaランク B 相当）

n 人の生徒が受けた、10^9 点満点のテストの採点結果 A_1, A_2, ..., A_n があります。あなたは合格点を自由に設定することができます。合格点が k 点のとき、k 点以上を取った生徒が合格で、k 点未満を取った生徒が不合格です。

q 個の整数 k_1, k_2, ..., k_q が与えられます。各 k_i について、合格点が k_i のときに合格する生徒の人数を答えてください。

なお、n, q の最大値はいずれも 200,000 です。

制約を見ると、生徒の人数 n は最大で 200,000 人で、与えられる合格点の候補 k の数は 200,000 です。k が与えられるたびに生徒ひとりひとりの点数を確認し、合格者数を求めるアプローチで解こうとすると、最悪で 200,000 * 200,000 回処理をする必要があり、これでは実行時間制限に間に合いません。

二分探索は、このような問題にも適用することができます。具体的には、単調性のある列の境界を求める状況に適用することができます。

以降では、簡単のために 0 始まりの添字で記述します。A_0, A_1, ..., A_{n-1} をソートします。すると、A_x >= k ならば、y >= x を満たすすべての y について A_y >= k であることから、A_i >= k を満たすような i の最小値 min_i がわかれば、合格者数の人数は n - min_i で求めることができます。ただし、A_i >= k を満たすような i がひとつも存在しない場合は、min_i を n とします。

min_i は、以下のようにして求めることができます。

/**
    A_i >= k を満たす最小の i を返す
    A_i >= k を満たす i が存在しない場合は n を返す
*/
binary_search(A : 数列, n : 数列のサイズ, k : 基準)
    // 探索範囲 [left, right]
    left = 0
    right = n
    
    // 探索範囲を狭めていく
    while left < right
        // 探索範囲の中央
        mid = (left + right) / 2

        if a[mid] < k then
            // a[0] ~ a[mid] は k 未満なので調べる必要が無い
            left = mid+1
        else
            right = mid
    
    return right

紙に長さ10程度のソートされた数列を書き、適当な値 k に対して binary_search がどのように動作するかを追ってみることをおすすめします。