線形探索（２）

単純な線形探索よりも効率の良い線形探索のアルゴリズムを考えます。繰り返しになりますが、単純な線形探索のプログラムでは、

1. index < size: indexがデータの末尾を越えていないかのチェック
2. data[ index ] == key : indexが指すデータの中身が目的の値でないかのチェック

の２つをチェックしなければなりませんでした。これから考えるアルゴリズムでは、データに「番兵」と呼ばれる特別な値を設置することによって、比較演算の回数を半減させます。下図は整数のデータが格納された配列から与えられた値を探索している様子を示しています。



この例でも、要素数が１２個の配列の中から８を探していて、配列の先頭から順番に各要素が８であるかどうかをチェックしています。重要なポイントは、データの末尾に番兵として目的の値である８を追加していることです。番兵を設置することによってデータの中に目的の値が存在することが保障されるので、探索している範囲がデータ数を超えてしまわないかのチェックを行う必要がなくなります。目的のデータが見つかったときの index がデータのサイズを超えていた場合（index　が size と等しい場合）、それは番兵を示すので、データに目的の値が存在しなかったことを示します。番兵を用いた線形探索のプログラムの例を以下に示します。

#include<iostream>
using namespace std;

#define MAX 10000
#define NOT_FOUND (-1)

int linearSearch( int data[], int size, int key ){
    int index = -1; // data[0]から検索を開始するため
    data[ size ] = key; // 番兵をセットする 

    while ( data[ ++index ] != key ); // 探索する

    if ( index == size ) return NOT_FOUND; // 番兵が機能した場合 
    else return index; // 目的の値を発見した場合 
}

09 行目でデータの末尾に番兵である key を設置します。その結果、メインループでの比較処理はdata[ ++index ] != key の１つしかありません。番兵がいるのでメインループの while( data[ ++index ] != key ); は必ず終了することが保障されます。つまり、データの範囲を超えてチェックしていまうという危険な処理を"番兵"が阻止します。メインループが終了した時の index の値が、目的の値を指します。データが見つからなかった場合は、index が番兵にたどりついてしまった場合、すなわち index が size に達してしまった場合です。