Cでリニアサーチ

アルゴリズムの中で代表的なものの一つがリニアサーチ（線形サーチ）。
バブルソートとかとあわせて、よくプログラミング言語の入門書に出てくる。
これは、単純に配列の中の要素と探索キーを比較するというもの。
・・・アルゴリズムと呼んでいいものだろうか。

int linearSearch(int array[], int key, int size){
　int n;
　for( n = 0 ; n < size ; n++ ){
　　if( array[n] == key ) return n;
　}
　return -1;
}

上記の実装では、一致するものが見つからない場合は-1を返している。
まあこの値はプログラムの仕様だから別になんでもいいが。
キーと一致した配列のインデックスを呼び出し元は知ることになる。

アルゴリズムの一般論として、シンプルなものはパフォーマンスが悪い。
この線形サーチは、小さい配列を扱うにはいいが要素数が大きくなると当然処理速度も落ちる。
大きな配列を扱うには、二分サーチを使う方がいいだろう。