バイナリサーチとは？
コンピュータ・サイエンスにおいて、バイナリサーチ（半値探索、対数探索、バイナリ・チョップとも呼ばれる）は、ソートされた配列の中でターゲット値の位置を見つける探索アルゴリズムである。バイナリサーチは、ターゲット値と配列の中間要素を比較する。もし両者が等しくなければ、ターゲットが横たわることができない半分が除外され、残りの半分で探索が続けられ、再びターゲット値と比較するために中央の要素を取り、ターゲット値が見つかるまでこれが繰り返される。残りの半分が空で検索が終了した場合、ターゲットは配列にない。

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

O(log n)の比較を行う。

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

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