線形探索と番兵法の比較

通常の線形探索アルゴリズムと、番兵法を導入した線形探索を比較してみます。

通常の線形探索では、配列の範囲チェックと要素比較を毎回同時に行います。

〔プログラム〕

 〇整数型: linearSearch(配列型(整数型): A, 整数型: key)
   整数型: i
   i ← 0
   while (i < A の長さ かつ A[i] ≠ key)
     i ← i + 1
   endwhile
   if (i < A の長さ)
     return i
   else
     return -1
   endif

特徴

• ループ条件に「範囲チェック (i < A の長さ)」が必要
• 1 回の比較に 配列範囲判定 ＋ 値比較 の2つが必要
• コードがやや複雑になる

番兵法では、配列の末尾に「探す値 (key)」を一時的に置くことで、必ず探索が終了する保証を作ります。

〔プログラム〕

 〇整数型: linearSearchSentinel(配列型(整数型): A, 整数型: key)
   整数型: n
   n ← A の長さ

   整数型: last ← A[n-1]      // 元の末尾を保存
   A[n-1] ← key                // 番兵をセット

   整数型: i ← 0
   while (A[i] ≠ key)
     i ← i + 1
   endwhile

   A[n-1] ← last               // 復元

   if (i < n-1 または last ＝ key)
     return i
   else
     return -1
   endif

特徴

• ループ条件は「A[i] ≠ key」だけで済む
• 配列範囲のチェックが不要
• 毎回のループでの比較が 1 回に減り、処理が簡潔

• 条件判定が簡単になり、処理が速くなる

範囲チェックが不要になるため、比較回数が少なく済む。

• アルゴリズムが明快

「必ず見つかる値（番兵）」を用意することで終了条件が単純になる。

• 教育的効果

探索アルゴリズムを学ぶとき、条件の単純化や工夫の大切さを理解できる。

※実際のプログラムでは差はわずかですが、低速な環境や処理を大量に繰り返す場合に効果が出ます。