【二分探索とは】探索アルゴリズム「バイナリサーチ」をやさしく解説

こんにちは。タクマ™ [@suwaru_blog] です。

コンピュータが 100 万個のデータの中から 1 つのデータを探し出すとき、
一体どのような計算をしているでしょうか？

もし先頭から順番にデータを探すと、末尾に目的のデータがあったら 100 万回の処理が走ります…
コンピュータはそんな非効率な探し方をせず、探索アルゴリズムというものを使います。

犯人探しクイズ

ある事件の 15 人の容疑者が一列に並んでいて、この中に 1 人の犯人がいます。
あなたは容疑者 1 人ずつに「犯人はどこですか？」と質問可能で、以下の返事を期待できます。

確実に 3 回以下の質問で犯人を見つけるにはどうしたらよいでしょうか。

容疑者が 3 人の場合で考える

まずは少ない数で考えてみましょう。
もし容疑者が 3 人しかいない場合、真ん中の 1 人に質問すれば一発で犯人がわかります。

もし真ん中が犯人じゃないとしても、その答えによって犯人確定できるのですね。

答え

犯人が潜んでいる範囲の真ん中の人に質問していけば、
確実に 3 回の質問で犯人を見つけることができます。

真ん中に質問すれば、容疑者が約半分に絞られるのがポイントです。

再帰的な構造

n 回の質問で確実に犯人確定できる容疑者数を P(n) としましょう。

ここから、以下の漸化式を立てることができます。

P(n) の閉じた式は 2^n+1 - 1 なので、
n 回の質問で確実に犯人確定できる容疑者数は 2^n+1 - 1 人になります。

バイナリサーチとは (二分探索)

先ほどの犯人探しクイズの考え方はコンピュータのデータ検索でも採用されています。
目的のデータを見つけるために、探索範囲の真ん中から調べる手法を「バイナリサーチ」といいます。

バイナリサーチは「二分法」や「二分探索」と呼ばれたりもします。

バイナリサーチを行うためには検索対象のデータは順序よく並んでいる必要があります。
データの順番がグチャグチャだったら、目的のデータが左右どっちにあるのか分からないからです。

バイナリサーチを実装する

以下 15 要素をもった配列データがあるとします。

var data = [16, 17, 23, 29, 31, 42, 45, 58, 62, 66, 67, 71, 78, 83, 88]

この前提なら、犯人探しクイズと同じく 3 回以内の探索で欲しい数字を見つけることができます。
たとえば 67 を探してみましょう。

ちゃんと 3 回以内で見つかるロジックになっています。

ソースコード

// 二分探索
function binarySearch(array, key) {
    var low = 0;
    var high = array.length - 1;
    var mid;
    var element;

    while (low <= high) {
        mid = Math.floor((low + high) / 2, 10);
        element = array[mid];
        if (element < key) {
            low = mid + 1;
        } else if (element > key) {
            high = mid - 1;
        } else {
           return mid;
        }
    }
    return -1;
}

// 第一引数の配列から、第二引数の値のインデックスを発見する
console.log(binarySearch([16, 17, 23, 29, 31, 42, 45, 58, 62, 66, 67, 71, 78, 83, 88], 67));

バイナリサーチは指数的爆発と相性がよい

このようにデータが 15 個くらいだったら、配列の先頭から 1 個ずつ調べることも可能です。

ですが、例えばデータが 2047 個あると、先頭から調べるのはかなり効率が悪いです。
その場合、バイナリサーチを使えば 10 回以内の探索で欲しいデータを見つけることができます。

前回、指数的爆発は「 2 の累乗され続けると発生する」と解説しました。
対してバイナリサーチは「検索対象を半分にしていく手法」なので起こっていることは正反対です。

バイナリサーチはデータ探索アルゴリズムの基礎なので、しっかりと覚えておきましょう。
競技プログラミングでも頻出です！

CS シリーズ

次回

前回