今回は二分探索を取り上げます。

検索:コンピューターの最もよくある利用法

「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。

配列:コンピューターがデータを扱う根本的な方法

そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。

現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1が合計八個入っています。なぜ一個ではないかというと、一個ではほとんどの用途であまりに非効率だからです。0と1が八個なので、このバイト一個で256種類の状態を表現することが出来ます。記号まで含めたアルファベット1文字がちょうど入る大きさです。

その各文字、いや各バイトがどこにあるかというのを示すのが番地(address)。コンピューターでデータを扱うというのは、ある番地にあるデータを取り出し、それを加工してまた番地を指定してそこに書き込むということの繰り返しから成り立っています。これもまた一種の検索です。

この「メモリーの何番地にあるデータをよこせ」「メモリーの何番地にデータを書き込め」という作業は、アルゴリズムを語る時にはO(1)で出来るということになっています。0番地も40億番地も、読み書きする時間は同じと見なす、ということです。

「見なす」、といいました。現在のコンピューターでは、「メモリーのどこにアクセスしても同じ時間で処理できる」ということは実は事実に反します。その番地が実際に仮想記憶に乗っていればものすごく遅くなりますし、逆にその番地がCPUのキャッシュに乗っていればものすごく速くなります。

しかしプログラミングにおいては「そのデータが実際はどこにあるのか」ということは気にしないくてもいいようになっています。というよりOSやCPUがよきに計らってくれるので、気にしたくてもなかなか出来ないということです。本書では、「ある番地にあるデータを読み書きする」、すなわち配列のアクセスのコストは常に一定、O(1)ということで話を進めて行きます。

線形探索:頭から見つかるまで探す

ただし、以上は「はじめからどこにデータがあるのかわかっている」場合の話です。いつもそれがわかっていればコンピューターはいりません。メモリーのどこかに望みのデータがあるがどう見つけるか。

一番簡単なのは、頭から順繰りに探すことです。積んである本の中から目的の本を探すときと全く同じです。最悪の場合、本は一番底にあるかも知れません。このように、頭から順繰りに探す場合、かかる時間はO(n)、すなわち探し物の数に比例します。このことから、この探索方法は「線形探索」(linear search)と呼ばれています。

実に単純ですが、探し物がそこにあるか、あったらしたらどこにあるかを確実に知ることが出来るという意味で決して間違った方法ではありません。

二分探索:分割征服(divide & conquer)アルゴリズムの基本

要素数 で
以下から を

    とはいえ、まだ探し物の数が100や200なら線形探索も気になりませんが、100万や200万ともなると人間の手ではお手上げ。これが10億とか20億ともなると、コンピューターでさえ苦しくなってきます。

    しかし、我々はコンピューターの助けを借りる前から、100万単位での探し物を平気でこなしてきました。その国を代表する図書館には、コンピュターが登場する前からそれくらいの蔵書はあったのですから。一体どうやってそれが可能だったのでしょう。

    答えは、簡単です。

    あらかじめ整理整頓しておけばいい。

    あらかじめ整理してあれば、いきなり頭から順繰りに探す必要はなくなります。

    二分探索法(binary search)は、この整理されたデータから目的のものを探すための単純で強力な方法です。その要諦は、まだ年齢が一桁のうちの娘達にも理解できるよう説明できます。

    1. まず「ここから」「ここまで」という範囲を決める
    2. 「ここから」「ここまで」のど真ん中を見てみる。見つかったらそれでおしまい。
    3. もしそれより「前」にあったら、「ここまで」を今見たところの一つ前に
    4. そうでなければ「ここから」を今見たところの一つ後ろにして
    5. また探す

    右側のデモとあわせてみれば、一目瞭然でしょう。

    これを素直にJavaScriptで書くと、以下のとおりとなります。

    function binary_search(array, value, head, tail){
  if (head > tail) return -1;                // 探索失敗
  var where = Math.floor((head + tail) / 2); // 真ん中
  if (value == array[where]) return where;   // 発見!
  if (value <  array[where]) tail = where-1; // あるとしたら前
  else                       head = where+1; // あとしたら後ろ
  // 探し直し
　return binary_search(array, value, head, tail);
}

    この方法がすごいのは、要素数が倍になっても繰り返しは一回しか増えないことです。別の言い方をすると、O(log n)のアルゴリズムということです。これがどれほどすごいかというと、たとえ100万要素あっても、たかだか20回程度の繰り返しで済むのです。これが線形探索なら最悪100万回です。

    実用上の工夫

    JavaScriptの場合、配列の最初と最後は配列自身が知っているので、こう書き直すことも出来ます。

    function binary_search(array, value){
  return (function(head, tail)
    if (head > tail) return -1;
    var where = Math.floor((head + tail) / 2);
    if (value == array[where]) return where;
    if (value <  array[where]) tail = where-1;
    else                       head = where+1;
    return arguments.callee(head, tail);
  })(0, array.length-1);
}

    再帰なしで書き直すと、以下のとおりとなるでしょう。

    function binary_search(array, value){
  var head = 0;
  var tail = array.length - 1;
  while (head <= tail){
    var where = Math.floor((head + tail) / 2);
    if (value == array[where]) return where;
    if (value <  array[where]) tail = where-1;
    else                       head = where+1;
  }
  return -1; // 探索失敗
}

    上では探索範囲が前にあるのか後ろにあるのかを不等号で決めていましたが、実際に配列にあるデータは数値だとは限りません。この探索範囲を決める関数を指定できるようにすれば、さらに使いやすくなります。

    function cmp_default(a, b){ return a == b ? 0 : a < b ? -1 : 1 };

function binary_search(array, value, cmp){
  if (!cmp) cmp = cmp_default;
  var head = 0;
  var tail = array.length - 1;
  while (head <= tail){
    var where = head + Math.floor((tail - head) / 2); // 後述
    var c     = cmp(array[where], value);     // 後述
    if (0 == c) return where;
    if (0 <  c) tail = where-1;
    else        head = where+1;
  }
  return -1; // 探索失敗
}

    ここで関数cmpは、探索範囲が前ならマイナス、後ろならプラス、そして探索に一致した場合には0を返すような関数です。こういった関数を比較関数(comparator)と言います。これなら配列中のデータの種類に関わらず、そのデータの種類にあわせた比較関数を使うことで対応できます。省略した場合は数値比較しています。

    上記では、以上に加えて、「真ん中」を割り出す演算をさらに注意深くしています。「aとb間を取る」のに(a + b) / 2と素直にやると、a + b がオーバーフローする可能性があるのです。それほど大きなデータを扱うことがなかったのでこれは見逃されてきましたが、最近になって何GBもあるようなデータを扱うケースが増えて来たことで問題が顕在化しました。JavaScript(正確にはECMAScript)の仕様上はこの問題は発生しないのですが、本書はなるべく他の言語にも移植しやすいコードを書くことにしているのでこういう書き方にしています。

    さらなる応用

    二分探索は、特定の秩序で並べられたデータの検索であればほぼ何にでも使える、実に応用範囲の広いアルゴリズムです。

    面白い応用としては、Suffix Arrayというものがあります。これは無秩序に並んだデータ、例えば一般的なテキストファイルに対応する秩序だったデータ構造を用意し、それに対して二分探索をかけることで、本来線形探索しかできなかったデータをO(log n)で検索するアルゴリズムです。これを使うとDVD一枚分の文書でも一瞬にして探索することが出来ます。

    見てのとおり、二分探索はコンピューターが相手でなくても使えるアルゴリズムです。あなたが今抱えている問題も、こういう風に分割して征服できるかも知れませんヨ。

    Dan the Binary Searcher