====== 線形探索と番兵法の比較 ======

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

----

===== 通常の線形探索 =====

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

〔プログラム〕
<code>
 〇整数型: 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
</code>

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

----

===== 番兵法を使った線形探索 =====

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

〔プログラム〕
<code>
 〇整数型: 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
</code>

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

----

===== 比較まとめ =====

|< 50% >|
^ 項目                ^ 通常の線形探索 ^ 番兵法ありの探索 ^
| ループ条件          | 範囲チェック＋値比較 | 値比較のみ |
| 1 回の比較コスト    | 2 回判定が必要       | 1 回判定で済む |
| コードの読みやすさ  | やや複雑             | シンプル |
| 実行速度（平均）    | 若干遅い             | 若干速い |

----

===== 番兵法のメリット =====

  * **条件判定が簡単になり、処理が速くなる**  
    範囲チェックが不要になるため、比較回数が少なく済む。
  * **アルゴリズムが明快**  
    「必ず見つかる値（番兵）」を用意することで終了条件が単純になる。
  * **教育的効果**  
    探索アルゴリズムを学ぶとき、条件の単純化や工夫の大切さを理解できる。

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