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行目

leftとrightという変数が探索の対象を表します。leftとrightの間が探索対象です。

7行目

ループです。leftがrightより大きくなったら一致するデータがなかったということでループ終了です。

8行目

中央のインデックスを計算します。

9〜15行目

中央のデータのキー値と検索値を比較し、検索値の方が小さければrightをmiddle-1にし、検索値の方が大きければleftをmiddle+1にします。一致すれば一致したデータを返して探索終了です。

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が探索している目的のものか最後にチェックし、条件を満たしているので最後のブレークポイントで止まります。

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