二分探索

二分探索とは

二分探索はソートされた配列に対して効率的に要素を検索するためのアルゴリズムです。

普通にfind()で前から探索を行うと最悪の場合O(n)の時間がかかります。ですが配列がすでに整列済みならもっと簡単に調べられますよね。 二分探索は配列の真ん中を取り、その大小で半分に範囲を絞り込んでいきます。この手法を使うとO(log n)の時間で要素を見つけることができます。

二分探索の実装例

上記のコードでは、1から100までのソート済み配列に対して二分探索を実装しています。

targetがNならfind()では平均でN/2回の比較が必要ですが、二分探索では最大でlog2(N)回の比較で済むことがわかります。例えばNが100の場合、find()では平均50回の比較が必要ですが、二分探索では最大でも約7回の比較で済みます。

探索の過程で比較回数をカウントし、結果とともに表示しています。find()ならtargetと同じ回数の比較が必要です。回数を比べてみて効率の違いを実感してみてください。

まとめ

ソートされた配列に対して効率的に探索を行うアルゴリズムである二分探索について解説・実装しました。

二分探索を使うことで、大規模なデータセットに対しても高速に要素を検索できるようになります。

すでにソートされた配列があるという前提は一見すると不思議かもしれませんが、整理されたデータを扱うことで効率化できるというのは重要な考え方です。是非とも覚えておいてください。