線形探索（１）

線形探索は最も単純で効率の悪いアルゴリズムと言えます。このアルゴリズムは、データセットの先頭から順番にデータを調べていきます。下の図は、整数のデータが格納された配列から、「与えられた値」を探索している様子を示しています。この例では、要素数が１２個の配列の中から「８」という数字を、配列の先頭から順番に探しています。目的のデータが見つかったときに処理が終了します。 。

このアルゴリズムはデータがどのような順番で配置されていても、データセットの中に目的のデータがあれば、正確にその要素を取得することができます。線形探索を実装したプログラムの例を以下に示します。

#include<iostream>
using namespace std;

#define MAX 10000
#define NOT_FOUND (-1)

int linearSearch( int data[], int size, int key ){
    for ( int index = 0; index < size; index++ ){
        if ( data[ index ] == key ) return index;    
    }
    return NOT_FOUND; // 見つからなかった場合
}

int main(void){
    int size, data[MAX], key;
  
    cin >> size;
    for ( int i = 0; i < size; i++ ) cin >> data[i];
    cin >> key;

    int result = linearSearch(data, size, key);
    
    if ( result == NOT_FOUND ) cout << "not found. " << endl;
    else cout << result << endl;

    return 0;
}

プログラムは非常に単純で、for ループを用いて、データの先頭から末尾まで調べていき、目的のデータが発見された時点で、そのインデックスを結果として返しています。見つからなかった場合は、特別な値として-1を返します

少し効率がよくなる実装方法。