番兵

　番兵とは、サーチの際にダミーデータを使用することにより、処理を簡潔化する手法の一つである。
　配列の内容を調べて、特定の値が存在するか否か、存在するとしたらどこにあるかを調べる場合がある。このような処理を一般に「サーチ」といい、端から順に調べていくという一番単純な方法を「リニアサーチ」と言う。
　リニアサーチのアルゴリズムは、VBで書くと以下のようになる。

' a() サーチ対象の配列
' n 有効なデータ数
' v サーチする値
' 戻り値：見つかった場合　　　・・・配列のインデックス
'         見つからなかった場合・・・-1　
Function search (a() As Integer, n As Integer, v As Integer) As Integer
    Dim i As Integer
    For i = 1 To n
        If a(i) = v Then          ' 見つかった場合の処理
            search = i
            Exit Function
        End If
    Next i
    search = -1                   ' 見つからなかった場合の処理
End Function

　このプログラムで悪いわけではないが、ループの脱出条件が二種類あるのが気に入らない（下記）。

値が見つかった場合（if節の中。Exit Functionで抜ける）
値が見つからなかった場合（Forを抜ける場合）

　番兵とは、ダミーデータの使用により、これら二つの条件を統合するものである。具体的には、最終要素の隣（データは入っていない）に、探すべき値を予め入れておく。これにより、値は「必ず見つかる」ことになり、上記 2.の条件を考えなくてもよいことになる。　具体的なプログラミング例は以下の如し。

Function search (a() As Integer, n As Integer, v As Integer) As Integer
    Dim i As Integer

    a(n + 1) = v  ' 番兵をセットする
    i = 1
    Do While a(i) <> v
        i = i + 1
    Loop
    If i > n Then      ’ 番兵にあたった場合
        search = -1    ’ データは存在しなかったことになる
    Else
        search = i     ’ データは存在している 
    End If
End Function

　これにより、ループをすっきりと記述できる。これが番兵の効果である。　一般にループを高速化するテクニックとして、ループの外でできるだけ準備をしておき、ループ内の処理を極力単純化すべきである。番兵は、この一番単純かつ有名な例と言える。