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

二分探索―半分ずつ絞り込んで効率アップ

　本連載を読まれてきた方なら逐次探索の効率が悪いことはすぐにお気付きになられることでしょう。総当たり的なアルゴリズムは効率が良くありません。どういった改善が考えられるでしょうか。

　探索の対象があらかじめソートされていれば効率的に探索することができます。

　例えば、あらかじめキーの昇順にソートされた100個のデータの集合があったとします。キー値60に対応するデータを探索するとします。

　この場合、100の半分の50番目のデータを取り出し、そのキー値と60を比較します。もし60よりも小さければ51番目から100番目のどこかに60があるはずです。もし60よりも大きければ1番目から49番目のどこかに60があるはずです。

　50番目のキー値が46だったとします。次は右側の真ん中のデータ、75番目のキー値を調べます。80だった場合は51番目から74番目の間に60があるはずです。

　このように探索の対象を半分ずつに絞り込んでいき、真ん中の値と比較していきます。これが二分探索です。

二分探索のソースコード

　それでは二分探索のソースコードを紹介します。先ほどの逐次探索のコードの末尾、「末尾1」のコメントの次の行に以下を追加してください。

<div id="bin">2分探索<br></div><hr>
<script type="text/javascript">
Array.prototype.binary_search = function(compare, n) {
  var left = 0
  var right = this.length - 1;
 
  while (left < right) {
    var middle = Math.floor(((right - left) / 2) + left);
    if (compare(n, this[middle].key) < 0) {
      right = middle - 1;
    } else if (compare(n, this[middle].key) > 0) {
      left = middle + 1;
    } else {
      return this[middle].value;
    }
    this.display("left:" + left + ", right:" + right);
  } 
 
  if (left != right) { return null; }
  if (this[left].key != n) { return null; }
 
  return this[left].value;
}
 
var i = 1;
var bin = array.clone();
bin.view_id = "bin";
bin.sort(function(a,b) { return compare(a.key,b.key); });
bin.display(bin);
bin.display("find: " + bin.binary_search(compare, 5));
</script><!-- 末尾2 -->

　プログラムを解説します。

3〜22行目

4、5行目

7行目

8行目

9〜15行目

28行目

デバッガで二分探索を見る

　デバッガでは3カ所のブレークポイントを設定するとよいでしょう。以下の3つの行にブレークポイントを設定してください。

var middle = Math.floor(((right - left) / 2) + left);
if (compare(n, this[middle].key) < 0) {
return this[left].value;

　最初にブレークポイントで停止したときには、left=0、right=6になっています。再開ボタンをクリックすると、middleが3になります。

　さらに、再開ボタンをクリックして見ると、n=5、middle=3のキー値4より大きいので、leftがmiddleの1つ右の4に変わります。どんどん再開ボタンをクリックしてみましょう。middleがleft(4)とright(6)の間の5に変わります。

　もう一度クリックします。middle=5のキー値は6なので、rightがmiddleの1つ左の4に変わります。left=rightとなるのでwhileループを抜けます。left=rightが探索している目的のものか最後にチェックし、条件を満たしているので最後のブレークポイントで止まります。

　次のクリックですべての処理が終了します。