2007年12月04日 08:30 [Edit]

アルゴリズム百選 - 二分探索(binary search)

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


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

二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、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


    この記事へのトラックバックURL

    この記事へのトラックバック
    英字かな交じりの文字列が100字くらいあるんだけど、30バイト以内ずつに分けたい
    ある文字列のうち、nバイト以内に収まるのは何文字か【メモ書き】at 2015年05月31日 00:13
    食後のデザートにちょうどよいサイズの問題。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか? 条件は次の通りです .. - 人力検索はてな 条件は次の通りです 集合Pはあ...
    algorithm - 最近点検索【404 Blog Not Found】at 2009年04月28日 23:49
    この記事へのコメント
    感謝します。自分の中で”あの方法”だったものが、
    二分探索という名前だと知ることができました。
    Posted by edry(えどりぃ) at 2009年04月29日 13:06
    nanto_viさん、
    に添削してもらえるとは光栄です。意見を取り入れてMath.floor版に差し替えて該当部分の表記も改めました。
    Dan the Revised
    Posted by at 2007年12月05日 02:09
    (文字数オーバーといわれたのでコメントを分割しています。)

    話を JavaScript に戻すと、ビットシフト演算子は内部的に数値を符号付きまたは符号なしの 32 ビット整数に変換するので、桁あふれを考慮すべき場面でこれらの演算子を使うことは不適切だと思います。例えば、a = 0x200000000, b = 0x400000000 としたとき、Math.floor((a + b) / 2) および a + Math.floor((b - a) / 2) は 0x300000000 となりますが、a + ((b - a) >>> 1) および a + ((b - a) >>> 1) では 0x200000000 となってしまいます。
    Posted by nanto_vi at 2007年12月04日 22:46
    JavaScript、というより ECMAScript に限定するなら、配列のインデックスとして有効な値は 0 〜 0xffffffff に限られ、かつ数値型の値は一般に IEEE 754 倍精度浮動小数点数として扱われるので、上記のコードで head + tail が桁あふれすることはありません。

    一般的なプログラミング言語に関して言えば、>>> 演算子が存在しない言語もあり、また符号桁の扱いを考えれば、>>> 演算子を用い、さらにそれを二で割るのと同様と言うのはやや不親切かと思います。
    Posted by nanto_vi at 2007年12月04日 22:45
    s/仮想記憶に乗っていれば/スワップアウトされていれば/
    Posted by まじかんと at 2007年12月04日 20:24
    yyyさん、
    あれまほんとだ。
    この場合、直し方は3とおりあって、
    1. yyyさんの通りif/elseの中身を入れ替える
    2. 不等号の向きを入れ替える
    3. 不等号の両辺を入れ替える
    なのですが、最初のコメントをそのままにしたかったのと、不等号の向きをそのままにしておきたかったので3.で直しました。
    #今度はきちんとtest suiteにかけました。やはりtestしないと駄目ですね。
    Dan the Debugged
    Posted by at 2007年12月04日 17:03
    最後の関数も、
    if (c < 0) head = where + 1;
    else tail = where - 1;
    じゃないの・・・?
    Posted by yyy at 2007年12月04日 15:06
    333さん、友水さん、
    そのとおりでした。実演用コードはちゃんと動いていたので、表記用コードの間違いがスルーされてたようです。
    Dan the Debugged
    Posted by at 2007年12月04日 09:48
    Math.floor(head + tail / 2);
    ではなくて
    Math.floor( (head + tail) / 2);
    ではありませんか?
    間違っていたらすみません。
    Posted by 友水 at 2007年12月04日 09:41
    「ここから」と「ここまで」が逆?
    Posted by 333 at 2007年12月04日 09:39