実装して学ぶ基本探索アルゴリズム ~線形探索と二分探索~

目次

探索とは

データ集合の中から目的の要素を探し出す処理のことです．
競技プログラミングでは与えられた配列に対して処理を行うことが多いので，覚えておくべきものの一つになります．
その中でも基本となるアルゴリズムは線形探索，二分探索，ハッシュ法になります．
では，早速それぞれのアルゴリズムの説明と実装に移っていきます．

線形探索(Linear Search)

配列の先頭から各要素が目的の値と等しいかどうかを順番に調べます．等しいものを見つけた時点でその位置情報を返し，探索を終了する単純なものになります．
もし末尾まで調べて目的の要素がなければ特別な値(競プロなどでは"-1"など指定されています．)を返します．
アルゴリズム効率の悪さはありますが，データの並び方に関係なく，利用することができます.
競プロでは計算量を考慮しなければいけませんが，まずはこれでいけるかどうか考えてみるといいかもしれませんね．
対応する問題はALDS1_4_A:Linear Searchです．
問題の意図としてはn個の整数を含むリストxとq個の重なりのない整数を含むリストyを比較し，リストyの要素がリストxに何個含まれているかを答える問題になっています．
では，早速実装していきましょう．
今回は素直な実装とpythonの特徴を生かした実装の二つを用意してみました．

素直な実装

N = int(input())
num_list = list(map(int, input().split()))
q = int(input())
search_num = list(map(int,input().split()))
ans = 0
for i in search_num:
    if i in num_list:
        ans += 1
print(ans)

最初の4行は入力を受け取っているだけなのであまり気にしないでください．if文でnum_listの中にsearch_num[i]が含まれているか確認しています．この時，n回の比較をしているので，オーダーはO(qN)となります．

pythonの特徴(set)を生かした実装

N = int(input())
num_list = list(map(int, input().split()))
q = int(input())
search_num = list(map(int,input().split()))
ans = 0
for i in set(num_list):
    if i in search_num:
        ans +=1
print(ans)

少し計算量の話を追加で書きます.
pythonの特徴を生かした実装で使ったsetは集合を表していてリストの中身の重なりのある整数を重なりのない状態にしています．また，setのオーダーはO(1)です(参考)．扱った問題ではn個のリストの中に同じ整数が含まれていることがあったので，多少計算時間が短くなると思います．
今回の問題ではNが大きくなれば計算量はもちろん増えますが，qにも依存しているので条件次第では計算時間が大きく変わるので問題文などをよく読んで解きましょう.
実際Atcoderのような競技プログラミングではPythonでO(n²)になると厳しいケースなどもあるので選ぶ探索アルゴリズムが重要になってきます．

二分探索(Binary Search)

二分探索ではデータの大小関係を利用しています．そのため，配列が整列されて管理されている場合，効率的に探索することができるアルゴリズムです．
基本的な動作は

• 配列全体を探索の範囲にする
• 探索が終了するまで以下の処理を繰り返す．
  1. 探索の範囲内の中央の要素を調べる
  2. 目的の値と中央の要素が一致した場合探索を終了する．
  3. 目的の値が中央の要素よりも小さければ二分したうちの前半部分を，
     大きければ二分したうちの後半部分を探索範囲として1.に戻る．

各計算ステップが終わるごとに調べる範囲が半分になっていくので，高速に探索を行うことができます．
対応する問題はALDS1_4_B:Binary Searchになります．
問題の意図は先ほどと変わらないのですが，注目して欲しいのが制約部分です．

• 整数のリストSは昇順に並んでいる．
• n ≤ 100,000 , q ≤ 50,000

つまり，入力はソートされた整数で与えられることと先ほどの線形探索だとO（qn）だったので 5.0 x 10⁹ となり計算量が先ほどの問題の1000 倍かかるようになっているということに注目して欲しいです．こういった場合に二分探索は威力を発揮します．
では早速実装して行ってみましょう．

def binary_search(num_list, key):
    left = 0
    right = len(num_list)
    while right > left:
        mid = (left + right)//2
        if num_list[mid] == key:
            return 1
        #前半部分に答えがある
        if num_list[mid] > key:
            right = mid
        #後半部分に答えがある
        elif num_list[mid] < key:
            left = mid + 1            
    return 0
            
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in T:
    ans += binary_search(S, i)
print(ans)

今回解いた問題は同じなので，線形探索のコードと二分探索のコードどちらとも提出してみました．
結果は次のようになります．

線形探索の結果

二分探索の結果

後半のテストケースになるにつれて(計算量が多くなるにつれて)計算速度に違いが大きく表れていることがわかると思います．
二分探索はその名の通り計算する範囲を半分にしていくので必要となる計算量はO(logn)となります．
今回の問題では n ≦ 100,000 までの範囲だったので二分探索自体は16回程度の探索回数で答えにたどり着きます．
二分探索を扱った問題は競技プログラミングでよく出てくるのでこれを機に一緒に覚えましょう!

ハッシュ法

ハッシュ関数と呼ばれる関数値によって，要素の格納場所を決定する方法です．データ構造の一種でハッシュテーブルと呼ばれる表を用いる探索アルゴリズムです．
要素の値を引数として関数を呼び出すだけでその位置を特定することができるので，データの特性によっては高速に探索することができます．
pythonの場合全く同じではないですが辞書型がこれに当たると思います．
該当する問題はあるのですが，pythonで解くと簡単に済んでしまうので今回は省略させていただきます.