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

  • このエントリーをはてなブックマークに追加
  • Pocket

こんにちは。iQeda [@iQeeeda] です。

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

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

今回は探索アルゴリズムの一つ「バイナリサーチ」について解説します。

犯人探しクイズ

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

  • 「犯人はわたしより左にいます」
  • 「犯人はわたしより右にいます」
  • 「犯人はわたしです」
    • 質問した相手が犯人の場合

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

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

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

  • 「犯人はわたしより左にいます」
    • 左が犯人確定
  • 「犯人はわたしより右にいます」
    • 右が犯人確定
  • 「犯人はわたしです」
    • 当人が犯人確定

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

答え

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

  • 【1回目】15 人のうち真ん中の人に質問する
    • 左の 7 人に犯人がいることがわかる
    • 右の 7 人に犯人がいることがわかる
    • 真ん中の当人で犯人確定する
  • 【2回目】7 人のうち真ん中の人に質問する
    • 左の 3 人に犯人がいることがわかる
    • 右の 3 人に犯人がいることがわかる
    • 真ん中の当人で犯人確定する
  • 【3回目】3 人のうち真ん中の人に質問する
    • 左の 1 人で犯人確定する
    • 右の 1 人で犯人確定する
    • 真ん中の当人で犯人確定する

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

再帰的な構造

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

  • P(0) = 1
    • 0 回の質問で確実に犯人確定できる容疑者数は 1 人
  • P(1) = 3
    • 1 回の質問で確実に犯人確定できる容疑者数は 3 人

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

  • P(n)
    • (n = 0) の場合: 1
    • (n > 0) の場合: P(n - 1) + 1 + P(n - 1)
      • 最初の P(n - 1) は「左にいる」という回答によって絞りこめる容疑者数
      • 1 はいま質問している容疑者のこと
      • 最後の P(n - 1) は「右にいる」という回答によって絞りこめる容疑者数

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 を探してみましょう。

  • 【1回目】15 要素の真ん中を調べる
    • 真ん中は 58
    • 58 < 67 なので、67 はこれより右側の範囲 (7要素) にあることがわかる
      • [62, 66, 67, 71, 78, 83, 88] まで絞り込めた
  • 【2回目】7 要素の真ん中を調べる
    • 真ん中は 71
    • 67 < 71 なので、67 はこれより左側の範囲 (3要素) にあることがわかる
      • [62, 66, 67] まで絞り込めた
  • 【3回目】3 要素の真ん中を調べる
    • 真ん中は 66
    • 66 < 67 なので、67 はこれより右側の範囲 (1要素) にあることがわかる
      • [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 回以内の探索で欲しいデータを見つけることができます。

データが 209 万 7151 個だったら 20 回以内の探索回数、
データが 21 億 4748 万 3647 個だったら 30 回以内の探索回数で済みます。

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

また、バイナリサーチの探索回数は 1 増えると 2 倍の検索対象に対応できるともいえます。
なので「指数的爆発が起きるときほどバイナリサーチは非常に有効」なのです。

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

CS シリーズ

次回

前回

お仕事ください!

僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。
なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。

カテゴリ「CS」の最新記事

最新記事

コメント

コメントを残す

*