サーチ（Search）とは，複数のデータの中から特定のデータを見つけ出す作業のことです。日本語では探索や検索と呼びます。
サーチのアルゴリズムには，ランダムなデータを取り扱えるものと，ソート済みのデータを取り扱うものとがあります。
リストサーチ（list search）
データのリスト構造とはA, B, C, ……のように，データが次々と連続している構造のことを言います。代表例は配列です。
そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを，ここではリストサーチと呼びます。
探索のアルゴリズム
- 線形探索
- 二分探索
- ハッシュ法
線形探索
線形探索という言葉は英語のLinear Searchの直訳です。線形探索はリストの先頭から終端に向かって目的の要素を探し出すアルゴリズムです。
目的の要素であるという判定は比較によって行います。
アルゴリズム分析
- リストの先頭から要素を取り出す
- 取り出した要素の値と探したい要素の値を比較する
- 一致すれば探索完了
- 一致しなければ 1. へ戻り次の要素を取り出す
かなりシンプルで理解し易いアルゴリズムです。
サンプルコード
線形探索のアルゴリズムを実装したsketchは次のとおりです。
線形探索のsketch。LinearSearch.pde
// 線形探索 Linear Search
// 番兵無し No Sentinel
final int NUMBER_OF_RANDOM_DATA = 500;
final String DATA_FILE_NAME = "RandomData.txt";
final int DIAMITER = 5;
final int SEARCHING_VALUE = 37;
ArrayList<Integer> nums = new ArrayList<Integer>();
int i = 0; // サーチ回数。drawする度にカウントアップ
void setup(){
//ランダムなデータの読み込み
loadData();
//ディスプレイウインドウの設定
size(NUMBER_OF_RANDOM_DATA,NUMBER_OF_RANDOM_DATA);
background(0,0,0);
frameRate(60);
stroke(255,0,0);
}
void loadData(){
String lines[] = loadStrings(DATA_FILE_NAME);
for(String val : lines){
nums.add(int(val));
}
}
void linearSearch(){
if (SEARCHING_VALUE == nums.get(i)) {
println("Hit!");
ellipse(i,nums.get(i),DIAMITER*2,DIAMITER*2);
exit();
}
}
void draw(){
println("Searching value is " + SEARCHING_VALUE);
if (i < NUMBER_OF_RANDOM_DATA){
//サーチ１パス
linearSearch();
//結果をプロット
println("Count " + i);
clear();
for (int k=0; k < nums.size(); k++) {
if ( k == i ) {
ellipse(k,nums.get(k),DIAMITER*2,DIAMITER*2);
} else {
ellipse(k,nums.get(k),DIAMITER,DIAMITER);
}
}
++i;
}
}
参考：
- http://www.codereading.com/algo_and_ds/algo/linear_search.html