JavaScriptで学ぶアルゴリズム②[2分探索]

外資系企業でソフトウェアエンジニアをしております、タロイモと言います。今日もよろしくお願いします。

前回は、O(n)とO(1)アルゴリズムの紹介をしました。

今回は、O(log n)アルゴリズムを紹介いたします。

O(log n)

O(log n)アルゴリズムはデータ量が増えても計算量が変わらないという特徴を持つので、素晴らしいアルゴリズムと言えるでしょう。

O(log n)アルゴリズムでは、2分探索（バイナリーサーチ）が有名です。

2分探索は、予めソート（整理）してあるデータから特定の値を探す時に利用します。

辞書で例えるとわかりやすいかもしれません。

50重音順に並んだ辞書があるとします。

「あ」「い」「う」「え」「お」、、、「わ」「を」「ん」で終わる辞書です。

ここで「ラーメン」という言葉を探してみるとします。

ラーメンの「ら」を調べる時、私たちはパッと「ら」のページを開くことができます。

しかし、コンピューターはそうはいきません。パッと「ら」を調べることができないのです。

そこでコンピューターは「あ」から探し始めます。

1から探し始めるのは線形探索ですね。少ないデータ量の辞書なら、線形探索で良いですが、今回の辞書は膨大な量があることを仮定すると1から探していくととんでもない時間がかかりそうです。

そこで一度辞書を半分に分けます。

すると、「は」「ひ」「ふ」「へ」「ほ」の「ふ」あたりで分けることになるでしょう。

「ふ」を真ん中にしたら、「あ」から数えるより「ふ」から数えた方が「ら」は近いことがわかります。

次にまた、「ふ」で半分に分けた後半の辞書を半分に分けます。
「ふ」から「ん」 を後半とすると、「ゆ」あたりが後半の真ん中にあるとわかります。

「ゆ」を真ん中にしたら、「ふ」から数えるより「ゆ」から数えた方が「ら」は近いことがわかります。

「ゆ」からのデータ量なら線形探索で探すことが簡単です。

簡単な例ですが、データ探索にかかる時間は約1/4になりました。

これが二分探索です。

2分探索をJavaScriptで表してみると以下のようになります。

let array = [1, 5, 10 ,15, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75];

function binary_search(key) {
 let searchLeft = 0;
 let searchRight = array.length - 1;
 let half;

 while (searchLeft < searchRight) {
   half = Math.ceil((searchRight + searchLeft) / 2);
   if (parseInt(key) === array[half]) {
     console.log(`${key}は配列の${half + 1}番目にあります。`);
     break;
   } else if (parseInt(key) < array[half]) {
     searchRight = half;
   } else if (parseInt(key) > array[half]) {
     searchLeft = half;
   } else {
     console.log("なし");
     break;
   }
 }
}

binary_search(15); //15は配列の4番目にあります。
binary_search(75); //75は配列の15番目にあります。
binary_search(76); //なし

今回はここまでとします。

次回はO^2であるソートアルゴリズムについて紹介します。

本日もご精読ありがとうございました。