値の探索 PHP編（paizaランク C 相当）

ソートされた数列 A = (A_1, A_2, ..., A_n) と、q 個の整数 k_1, k_2, ..., k_q が与えられます。各 k_i について、数列 A に含まれているなら Yes と、含まれていないなら No と出力してください。

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

q 回線形探索を行うことで解けそうですが、制約を見ると数列 A のサイズは最大で 200,000 、q も最大で 200,000 ですから、最悪で 200,000 * 200,000 回処理をする必要があり、これでは到底処理が終わりません。何か工夫をする必要があります。

A がソート済みであることに注目します。A の真ん中の要素が k 未満であれば、A の前半分の要素もすべて k 未満であることがわかります。つまり、A の前半分について探索する必要が無くなります。逆に、A の真ん中の要素が k より大きければ、A の後ろ半分の要素もすべて k より大きいので、A の後ろ半分について探索する必要が無くなります。

つまり、「対象とする探索範囲の中央の値」と「探索したい値」を比較することで、探索範囲を半分にすることができます。このようなアプローチを 二分探索 と呼びます。

実装は、探索範囲の始点と終点を変数として持ち、探索範囲を半分にする処理を探索範囲が十分小さくなるまで繰り返すようにするとよいです。

・区間について

本問題集の問題文・解説では、開区間・閉区間 をそれぞれ (a, b)・[a, b] と表記します。開区間は両端点を含まない区間を、閉区間は両端点を含む区間をそれぞれ指します。つまり、

• (1,5) ... 1 < x < 5 を満たす x からなる区間


• [1,5] ... 1 ≦ x ≦ 5 を満たす x からなる区間

となります。

また、半開区間を (a, b] や [a, b) と表記します。これは一方の端点が区間に含まれており、もう一方の端点が区間に含まれていないような区間を指します。つまり、

• (1,5] ... 1 < x ≦ 5 を満たす x からなる区間


• [1,5) ... 1 ≦ x < 5 を満たす x からなる区間

となります。

二分探索をおこなう際は、区間をどのような形で持つか (開・閉・半開) を問題に合わせて適切に選択する必要があります。

本問においては、閉区間で持つのがよいでしょう。

/**
ソート済みの数列 A に 値 k が含まれているなら true を、含まれていないなら no を返す
*/
binary_search(A : 数列, n : 数列のサイズ, k : 探索する値)
    // 探索範囲 [left, right]
    left = 0
    right = n-1
    
    // 探索範囲を狭めていく
    while left <= right

        // 探索範囲の中央
        mid = (left + right) / 2

        if A[mid] == k then
            return true
        else if A[mid] < k then
            left = mid+1
        else 
            right = mid-1
    
    return false