Binary Search (二分探索)

世界中の建物の高さを小さい順にすべて並べたリストを想像してください。最初の要素は世界で一番低い建物、最後の要素は一番高い建物になります。ここで、ある建物の高さを表すクエリの数値が与えられたとき、その高さを持つ建物のリスト上の位置（インデックス）を答えるゲームをすることにします。もしその高さの建物が存在しない場合は -1 を返します。

単純な方法としては、配列の先頭から末尾まで for ループで要素を順番にチェックするやり方があります。しかし最悪の場合、要素数を n とすると、各クエリに対して最大で n 回の比較を行うことになります。

h = [...]                # 建物の高さが小さい順に並んだリスト
q = int(input())         # クエリとして与えられる建物の高さ

for i, height in enumerate(h):
    if height == q:      # 要素が見つかった場合
        print(i)         # インデックスを出力
        break            # そのままループを終了
else:                    # （else はループが break されなかった場合）
    print(-1)            # 見つからなかった場合は -1 を出力

しかし、リストがすでに昇順でソートされていることを考えると、無駄な操作がたくさん含まれていることに気づきます。先頭から末尾まで順番にチェックするのではなく、もっと効率的に正しいインデックスにたどり着けるはずです。

要素が小さい順に並んでいるという特性を使えば、まずリストの中央要素を見て、その要素が q より小さいか大きいかで、扱うべき半分を捨てるアプローチが可能になります。もし中央の要素が q より小さいなら、左半分を全部捨てて右半分だけに絞り込みます。逆に中央の要素が q より大きければ、右半分を捨てて左半分だけを探索します。こうして中央要素を見ながら探索範囲を半分ずつ捨てていき、目的の要素を探す方法こそが Binary Search (二分探索) アルゴリズムです。

h = [...]                # 建物の高さが小さい順に並んだリスト
q = int(input())         # クエリとして与えられる建物の高さ

l, r = 0, len(h)         # 答えは常に [l; r) の区間に存在すると仮定（r は排他的）
while r - l > 1:         # 少なくとも1つは探索対象の要素が残っている間ループ
    mid = (l + r) // 2   # 中央のインデックスを取る
    if h[mid] > q:       # h[mid] > q の場合 => 右半分を捨てる
        r = mid
    else:                # h[mid] <= q の場合 => 左半分を捨てる
        l = mid

# 最終的に h[l] がクエリの要素と一致しているか判定
print(l if h[l] == q else -1)

たとえば、建物の高さが [20, 22, 23, 23, 34, 49, 52, 55, 58] という配列 h において、高さ 49 の建物のインデックスを求めたいとします。

このアルゴリズムでは、以下のようにいくつかの反復を行います:

1. mid = (0 + 9) // 2 = 4 ⇒ h[4] = 34 ≤ 49 ⇒ 左部分を捨てて右に絞る

2. mid = (4 + 9) // 2 = 6 ⇒ h[6] = 52 > 49 ⇒ 右部分を捨てて左に絞る

3. mid = (4 + 6) // 2 = 5 ⇒ h[5] = 49 ≤ 49 ⇒ 左部分を捨てて右に絞る

4. l = 5, r = 6 ⇒ r - l == 1 ⇒ ループ終了。最終的に h[5] = 49 を出力する。

この例だけだとそこまで大きな効率差は実感できないかもしれませんが、もし建物が 100 億棟あったらと考えてみてください。単純に先頭から末尾まで順に探す方法では最悪 100 億回の比較が必要ですが、二分探索では探索対象を毎回半分に分割して捨てていくため、はるかに少ない比較回数で済みます。実際に 100 億要素を毎回半分にしながら探すと、何回ぐらいループすれば済むかを見てみましょう:

もし 100 億要素を 1 秒ずつ順番にチェックする線形探索のアルゴリズムがあったら、完了するまでに 317 年かかります。しかし二分探索なら 32 秒で終わります。

これは の計算量と の計算量の違いです。

Challenge

学生の数 n 人がいて、それぞれが 1 から 4 の間の GPA を持っているとします（1 が最低で 4 が最高）。さらにいくつかの合格基準となるしきい値（threshold）が与えられるとき、そのしきい値以上を満たして次の学年に進級できる学生の数を答える問題です。

入力

最初の行には学生の数を示す整数 n (1 ≤ n ≤ ) が与えられます。

次の行には、昇順に並んだ n 個の浮動小数点数が与えられ、これは各学生の GPA (1 ≤ ≤ 4) を表します。

3 行目にはしきい値の数を表す整数 q (1 ≤ q ≤ ) が与えられます。

最後の行には q 個の浮動小数点数が与えられ、これは合格基準を示す値 (1 ≤ ≤ 4) です。

出力

q 行を出力し、各行 i には、与えられたしきい値 を満たして次の学年に進級できる学生の数を出力してください。

例