Firebugで探索アルゴリズムを見ていこう：コーディングに役立つ！ アルゴリズムの基本（6）（2/4 ページ）

[山下寛人，オイシックス株式会社]

逐次探索―キーを総当りで探す力業

　それでは最も単純なアルゴリズム、逐次探索を紹介しましょう。単にキーを総当たりで比較して一致したらそれに対応する値を返すというものです。

　先ほどのプログラムの65行目、「ここから」のコメントの次の行に以下のコードを追加してください。

<div id="seq">逐次探索<br></div><hr>
<script type="text/javascript">
Array.prototype.sequential_search = function(compare, n) {
  for(var i = 0; i < this.length; i++) {
    this.display("search index:" + i);
    if(compare(this[i].key, n) == 0) { return this[i].value; }
  }
 
  return null;
}
 
var seq = array.clone();
seq.view_id = "seq";
seq.display(seq);
seq.display("find: " + seq.sequential_search(compare, 5));
</script><!-- 末尾1 -->

　3行目から10行目が逐次探索のプログラムです。

　引数compareはキーの一致条件を定義する関数です。数値なので数値が等しいときに0を返すようにしていますが、カスタマイズすることもできます。

　4行目からfor文で配列の要素数分ループして、キーが検索条件nに一致するかどうか調べています。

デバッガで逐次探索を見る

　とても簡単なプログラムですが、練習のためにデバッガを使ってみましょう。

　HTMLファイルをFirefoxで開きます。逐次探索の結果が表示されると思います。「表示」→「Firebug」をクリックします。

　ウィンドウの下の部分にFirebugが出てきたら、「スクリプト」をクリックします。

　「スクリプトパネルは停止しています」と表示された場合は、「スクリプト」にチェックを入れ、「ローカルファイルで選択された機能を有効にします」をクリックします。

　スクリプトのソースが表示されます。下にスクロールして71行目（if文がある行）まで進め、左の「71」をクリックします。赤い丸が表示されます。ここがブレークポイントになります（if文をブレークポイントにしてもうまくいかない場合があるようです。その場合は上下の行や改行を入れてブレークポイントを設定してみてください）。

　Firefoxのリロードボタンをクリックします。プログラムの実行が設定したブレークポイントで停止します。

　ソースの右側にはそのときの変数の内容が表示されます。「this」の左のプラス記号をクリックすると、配列の内容も表示されます。

　探索するキーnの値は5、iの値は0、それに対応するkeyは1で一致しません。

　再開ボタン（水色の右向きの三角）をクリックします。iの値が1に変わります。さらに再開ボタンをクリックするとiの値が増えていきます。

　画面には「search index:」という行が表示されていきます。iが4のときにもう一度再開ボタンをクリックすると探索が成功になり、処理が最後まで終了になります。