ALDS1_4_A:

数列 $S$ の中に $T$ の各要素が含まれるかどうかを線形探索によって調べます。線形探索は配列の先頭から各要素が目的の値と等しいかどうかを順番に調べます。等しいものが見つかった時点でその位置を返し探索を終了します。

線形探索はfor ループを用いて次のように実装することができます。

1 linearSearch()
2   for i が 0 から n-1 まで
3     if A[i] と key が等しい
4     return i
5   return NOT_FOUND

この線形探索は「番兵」を用いた実装の工夫で定数倍の高速化が期待できます。番兵とは、配列などの要素として設置される特別な値で、ループの制御を簡略化する目的などで使われるプログラミングテクニックの１つです。線形探索では、次のように探索対象の配列の末尾に目的のキーをもつデータを番兵として設置します。

番兵を用いた線形探索は次のように実装することができます。

1 linearSearch()
2   i = 0
3   A[n] = key
4   while A[i] と key が異なる
5     i++
6   if i が n に達した
7     return NOT_FOUND
8   return i

２つのコードの違いは、メインループにおける比較演算の数です。１つ目のコードでは for ループの終了条件とキーとの比較演算の２つが必要です。一方、２つ目のコードでは、不等価演算１つですみます。番兵によって while ループが必ず終了することが保障されているため、終了条件を省くことができます。

番兵の考え方は、効率化に加えて、多くのアルゴリズムの実装において、コードを読みやすく、あるいは簡略化するテクニックとして用いられています。

線形探索は $O(n)$のアルゴリズムですが、番兵を使った実装は定数倍の高速化が見込まれ、大きなデータに対して効果が期待できます。

この問題（ALDS1_4_A: Linear Search）は、$n$ 個の要素の配列に対して $q$ 回の線形探索を行って、$O(qn)$ のアルゴリズムで解くことができます。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。