探索アルゴリズム

配列に格納された多くのデータから、ある特定の一要素を探し出すという 処理は頻繁に必要になる。ここまでのC言語の知識では、 多くのデータを格納する場合は配列変数を利用した。ここでは 配列変数に入っているデータからある特定のデータを探すときの アルゴリズムについて簡単に触れる。

逐次探索

検索対象物が気まぐれな順番で格納されている場合には、

配列変数の先頭から順に探して行く

より他の方法はない。このような場合はforループを利用して、 

  /* int data[] に数値たくさん入っていると仮定する */
  /* データの個数は n だとする */
  for (i=0; i<n; i++) {
    if (探したい値 == data[i]) {
        printf("%d番目にあったよ!\n", i);
	break;
    }
  }

のようにすればよい。

for (iを0から配列の終端まで回す) {
  配列のi番目のデータと探したいデータを比較
   → 同じだったら「発見!」
}

という探すための方法であることに注意すること。このような方法を 逐次探索、又は線形探索という。

二分(にぶん)探索

先述の逐次探索は

という特徴がある。前者の点はしばしば問題となり、データが100件のときに 1秒でみつかっていたものが、1000件になったとたんに10秒、1000件で100秒… と待ち時間が飛躍的に増大してすぐに使いものにならなくなる。

これを解決するため、あらかじめ小さい順にデータを並べておき 常に真中真中を探して行くことで比較回数が飛躍的に減少させる方法がある。 これを二分探索と呼ぶ。

たとえば、「1から100までの数当てゲーム」をするときに、

A君: 「いくつだー?」
B君: 「1でしょ!」
A君: 「ぶぶー。」
B君: 「じゃあ2でしょ!」
A君: 「ぶぶぶー。」
B君: 「じゃあ3でしょ!」
A君: 「ぶぶー。」
B君: 「じゃあ4でしょ!」
A君: 「それじゃあ日がくれちゃうよ…」

のように端から探していたのでは効率が悪い。このようなときは 正解が含まれる範囲の常に中央を調べて行くと効率がよい。

探す場所 解の存在する範囲
A君: 「いくつだー?」
B君: 「50でしょ!」
1   100
A君: 「ぶぶー。もっと上だよ」
B君: 「じゃあ75でしょ!」
1     100
A君: 「ぶぶぶー。もっと上だって」
B君: 「じゃあ88でしょ!」
1     100
A君: 「ぶぶー。もっと下だよ」
B君: 「じゃあ81でしょ!」
1       100
A君: 「惜しいね。もっと上だよ」
B君: 「じゃあ84でしょ!」
1       100
A君: 「正解!」
B君: 「やった!」
  

このような方法だと探す対象が倍の個数になっても探すための比較回数は 一回程度増えるだけですむ。

これは探す対象が必ず小さい順に並んでいる必要がある。 普段これに似た探し方をしているものに、辞書で英単語を探す作業がある。 辞書では必ず単語はアルファベット順に並んでいるので、探したいものが 開いたページより後ろにあるか前にあるかが確実に分かるので、 そのページより後ろにあると分かればそこに指を挟んでそれより右側を探し、 そのページより前にあると分かればそこに指を挟んでそれより左側を探し、… という風に挟む指をどんどん狭めていくことで、数千ページの中から 目的とする単語を10秒程度で探すことができる。

これをプログラムで表現すると次のようになる。

 int left = 0;                // 探す範囲の左端
 int right = MAXDATA;         // 探す範囲の右端(defineしてある)
 int middle = (right+left)/2; // 真中
 while (right-left >= 0) {
   if (探したい値 < data[middle]) { // もし真中の値のほうが大きかったら
     right = middle-1;        // 右端を middle の一個左に設定
   } else if (探したい値 > data[middle])//もし真中の値のほうが小さかったら
     left = middle+1;         // 左端を middle の一個右に設定
   } else {
     // 発見!
     // 見付かった場合の処理
     break;
   }
   middle = (right+left)/2;        //真中を再計算
 }
目次