２分探索

ウィキペディア

二分探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/24 16:42 UTC 版)

探索 > 二分探索

二分探索

クラス	探索アルゴリズム
データ構造	配列
最悪計算時間	$O\left(\log n\right)$ 二分探索アルゴリズムの視覚化。探索目標値は7である。 二分探索（英: binary search）もしくはバイナリサーチとは、計算機科学において整列配列の中から目標の値の位置を見つけ出す探索アルゴリズム。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。 二分探索は対数時間で動作するアルゴリズムであり、最悪のケースにおいて比較演算を $O(\log n)$ 二分探索の手順。 function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := L + floor((R - L) / 2) if A[m] < T then L := m + 1 else if A[m] > T then R := m − 1 else: return m return unsuccessful ${\frac {R-L}{2}}$ 二分探索は近似一致の計算にも応用できる。探索対象値の5が配列中に存在しない場合にも二分探索によって順位 (Rank)、直前要素 (Predecessor)、直後要素 (Successor)、最近接要素 (Nearest neighbor) が取得できる。 上記の手続きは完全一致の判定のみを行って目標値の位置を見つけるものである。しかし、二分探索は整列配列を対象としているため、近似一致の判定を行うように拡張することは容易である。たとえば、与えられた値に対して、順位（より小さい要素の数）、直前要素（次に値が小さい要素）、直後要素（次に値が大きい要素）、最も近い要素を求めるなどである。2つの値について順位を求めることで、それらの間にある要素数を求める範囲クエリも実行可能である。 順位クエリは左端要素を求める手続きによって実行できる。 直前要素クエリは順位クエリによって実行できる。目標値の順位が $r$ 二分探索を表す木構造。ここで探索対象となっている配列は $[20,30,40,50,80,90,100]$ 二分探索の最悪ケースでは、木構造の探索が最も深いレベルに到達する。最良ケースとなるのは目標値が配列の中央要素と一致したときである。 二分探索の性能のうち比較回数に関する部分は、手続きを二分探索木で表すことで評価できる。二分探索木の根ノードは配列の中央要素である。その子ノードは、左側が配列の前半の中央要素、右側が後半の中央要素となる。それ以降も同様に構築される。探索は根ノードから開始され、現在のノードの値を目標値と比較して大小に応じて左右の部分木をたどっていく。 最悪の場合、二分探索は比較ループを ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ 二分探索木は二分探索と類似したアルゴリズムで検索される。 二分探索木は二分探索の原理に基づいて機能する二分木のデータ構造である。すべてのレコードが整列しており、各レコードの探索は二分探索に似たアルゴリズムによって平均して対数時間で行うことができる。二分探索木では挿入や削除の処理も平均で対数時間となり、整列配列における線形時間の挿入・削除より高速となりうる。また二分木は範囲検索や近似検索など整列配列で可能なすべての操作が実行可能である。 しかしながら、実際の二分探索木は完全に平衡ではない可能性が高く、そのため検索効率では整列配列の二分探索に劣るのが普通である。ノードの自動的な再配置によって自己平衡を行う平衡二分探索木においても、理想的な最小階層数の構造が得られることはまれである。平衡でない二分探索木では、内部ノードの多くが子ノードを1つしか持たず探索時間が平均・最悪ともに ${\textstyle n}$ ユニフォーム二分探索では、上限・下限のインデックスではなく、現在の中点と2つの次の中点候補との間のインデックス差を記憶する。 ユニフォーム二分探索 (uniform binary search) では、配列インデックス範囲の上限と下限を記憶するのでなく、現在の中央要素と次の反復における中央要素のインデックス差を記憶する。具体的には、各回の反復におけるインデックス差を格納したルックアップテーブルをあらかじめ計算しておく。たとえば、0から10までのインデックスを持つ11要素の配列を探索する場合、最初の中央要素のインデックス $m$ 指数探索の概念図。長い配列から探索対象値を含む範囲の部分配列を抜き出し、それに対して二分探索を実行する。 指数探索は二分探索を無限長のリストに拡張したものである。このアルゴリズムはまず「インデックスが2のべき乗であり、かつ探索対象の値より大きい最初の要素」を見つけることから始め、そのインデックスを上限に設定した上で二分探索に切り替える。探索対象の位置を ${\textstyle x}$ 線形補間による内挿探索の概念図。このケースでは、配列内の目標値の位置が正確に推定されため探索が不要となっている。実装によっては目標値の位置を推定するために別の関数が用いられる。 内挿探索では、中間点を計算するのではなく、要素の最小値と最大値、ならびに配列の長さを考慮して目標値の位置を推定する。その前提には、中間点は多くの場合で最良の推定位置ではないという点がある。たとえば、目標値が要素の最大値に近い場合、その値は配列の末尾近くに位置している可能性が高い。 一般的には内挿関数として線形補間が用いられる。配列を $A$ フラクショナル・カスケーディングでは、カスケードされた配列のそれぞれに、前段の配列から1つおきで抽出した要素へのポインタが織り込まれる。これにより、最後の配列に対して二分探索を行うだけで全ての配列を探索するのに近い結果が得られる。 フラクショナル・カスケーディング は、複数の整列配列に対して同じ要素を探索する際に、二分探索によって高速な探索を行う手法である。配列を個別に探索する場合、 ${\textstyle k}$ ノイズのある二分探索では、比較処理が一定の確率で誤った結果を返す。 ノイズのある二分探索 (noisy binary search) は配列要素の比較に確実性がない問題に対するアルゴリズムであり、各回の比較結果が一定の確率で誤っているにもかかわらず所定の正確さで目標値の位置を見つけ出すことができる。この種の手法はいずれも、平均して少なくとも $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$; book version . Stroustrup, Bjarne (2013). The C++ programming language (4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2  外部リンク NIST Dictionary of Algorithms and Data Structures: binary search Comparisons and benchmarks of a variety of binary search implementations in C Archived 25 September 2019 at the Wayback Machine.