バイナリサーチとは？
コンピュータサイエンスにおいて、バイナリサーチ（half-interval search, logarithmic search, or binary chop, とも呼ばれる）は、ソートされた配列内の目標値の位置を求める検索アルゴリズムなのだ。バイナリサーチでは、目標値と配列の中間要素を比較する。両者が等しくない場合、ターゲットが存在できない半分を除外し、残りの半分で探索を続け、再び中央の要素を取ってターゲット値と比較し、ターゲット値が見つかるまでこれを繰り返す。残りの半分が空っぽのまま探索が終了した場合、ターゲットは配列の中に存在しないことになります。

バイナリサーチは、最悪の場合、対数時間で実行されるので

O(log n)個の比較、ここで

n は配列の要素数なのだ。 バイナリサーチは小さな配列を除いて線形探索より高速なのだ。ただし、バイナリサーチを適用するためには、まず配列をソートする必要がある。ハッシュテーブルのように、バイナリサーチよりも高速に検索できるように設計された特殊なデータ構造もある。しかし、バイナリサーチの方がより広い範囲の問題を解決することができ、例えば、配列に対象が存在しない場合でも、対象に対して配列の中で次に小さい要素や次に大きい要素を見つけることができる。

バイナリサーチには数多くのバリエーションがあるのだ。特に、分数カスケード法は、複数の配列の中から同じ値を探すバイナリサーチを高速化する。フラクショナルカスケードは、計算幾何学や他の多くの分野におけるいくつかの検索問題を効率的に解決する。指数関数的探索は、バイナリ探索を無限のリストに拡張する。バイナリサーチツリーとB-treeデータ構造はバイナリサーチに基づくものなのだ。
バイナリサーチは、ソートされた配列の中から目的の値の位置を見つける検索アルゴリズムなのだ。対象値が存在し得ない半分を除外する。残りの半分にある値を検索する。これは、目標値が見つかるまで、目標値と比較するために中間要素を繰り返すことで続けられます。
バイナリサーチは、小さな配列を除き、線形サーチよりも高速なのだ。