番兵法を用いた線形探索

要素が直線上に並んだリスト（配列）からの探索は、リストの先頭から順番に走査して探索対象と同じかどうかを確認することで実現できます。これを線形探索、もしくは逐次探索と言います。

Python での実装例を以下に示しています。

L = [1, 9, 2, 5, 4, 7]
def linear_search(search_obj):
    index = 0
    while True:
        if index == len(L): # $1
	    # 探索失敗
        if L[index] == search_obj: # $2
	    # 探索成功
	index += 1

線形探索では、各繰り返しの中で

1. 探索対象と同じ（イコール）か: $2
2. 末尾まで探索したか: $1

の２点を判定します。単純な判定ですが、探索リストサイズが大きいとそのコストは無視できないものになります。

「番兵法（sentinel method）」は、上記のうち、「2.」を削除することで探索コストを半分に削減する探索メソッドです。

具体的には、探索対象と同じ値（番兵と呼ぶ）を探索リストの末尾にあらかじめ挿入しておきます。そうすることで、リストの末尾まで探索をすると必ず探索対象が見つかります。
例えば、L = [1, 9, 2, 5, 4, 7] のリストから「５」を探索したいとします。L の末尾に探索対象である「５」を番兵として挿入します。つまり、走査するリストは L' = [1, 9, 2, 5, 4, 7, 5] になります。リストの末尾まで走査すれば、必ず検索対象を発見することができるので、index の確認は、最後に１回行うだけで十分になります。

Python で実装した番兵法の例を以下に示します。

L = [1, 9, 2, 5, 4, 7]
def sentinel_search(search_obj):
    # リストの末尾に番兵を挿入
    L.append(search_obj)
    index = 0
    while True:
        if L[index] == search_obj: # $2
	    if index + 1 == len(L): # $1
	        # 番兵が探索された（探索失敗）
	    else:
	        # 探索成功
	index += 1