にぶん‐けんさく【二分検索】
読み方:にぶんけんさく
二分探索
クラス | 探索アルゴリズム | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
データ構造 | 配列 | ||||||||||||||
最悪計算時間 |
![]() 二分探索(英: binary search)もしくはバイナリサーチとは、計算機科学において整列配列の中から目標の値の位置を見つけ出す探索アルゴリズム[1][2]。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。 二分探索は対数時間で動作するアルゴリズムであり、最悪のケースにおいて比較演算を 上記の手続きは完全一致の判定のみを行って目標値の位置を見つけるものである。しかし、二分探索は整列配列を対象としているため、近似一致の判定を行うように拡張することは容易である。たとえば、与えられた値に対して、順位(より小さい要素の数)、直前要素(次に値が小さい要素)、直後要素(次に値が大きい要素)、最も近い要素を求めるなどである。2つの値について順位を求めることで、それらの間にある要素数を求める範囲クエリも実行可能である[8]。
二分探索の性能のうち比較回数に関する部分は、手続きを二分探索木で表すことで評価できる。二分探索木の根ノードは配列の中央要素である。その子ノードは、左側が配列の前半の中央要素、右側が後半の中央要素となる。それ以降も同様に構築される。探索は根ノードから開始され、現在のノードの値を目標値と比較して大小に応じて左右の部分木をたどっていく[3][11]。
最悪の場合、二分探索は比較ループを 二分探索木は二分探索の原理に基づいて機能する二分木のデータ構造である。すべてのレコードが整列しており、各レコードの探索は二分探索に似たアルゴリズムによって平均して対数時間で行うことができる。二分探索木では挿入や削除の処理も平均で対数時間となり、整列配列における線形時間の挿入・削除より高速となりうる。また二分木は範囲検索や近似検索など整列配列で可能なすべての操作が実行可能である[19][24]。
しかしながら、実際の二分探索木は完全に平衡ではない可能性が高く、そのため検索効率では整列配列の二分探索に劣るのが普通である。ノードの自動的な再配置によって自己平衡を行う平衡二分探索木においても、理想的な最小階層数の構造が得られることはまれである。平衡でない二分探索木では、内部ノードの多くが子ノードを1つしか持たず探索時間が平均・最悪ともに ユニフォーム二分探索 (uniform binary search) では、配列インデックス範囲の上限と下限を記憶するのでなく、現在の中央要素と次の反復における中央要素のインデックス差を記憶する。具体的には、各回の反復におけるインデックス差を格納したルックアップテーブルをあらかじめ計算しておく。たとえば、0から10までのインデックスを持つ11要素の配列を探索する場合、最初の中央要素のインデックス 指数探索は二分探索を無限長のリストに拡張したものである。このアルゴリズムはまず「インデックスが2のべき乗であり、かつ探索対象の値より大きい最初の要素」を見つけることから始め、そのインデックスを上限に設定した上で二分探索に切り替える。探索対象の位置を 内挿探索では、中間点を計算するのではなく、要素の最小値と最大値、ならびに配列の長さを考慮して目標値の位置を推定する。その前提には、中間点は多くの場合で最良の推定位置ではないという点がある。たとえば、目標値が要素の最大値に近い場合、その値は配列の末尾近くに位置している可能性が高い[40]。
一般的には内挿関数として線形補間が用いられる。配列を フラクショナル・カスケーディング は、複数の整列配列に対して同じ要素を探索する際に、二分探索によって高速な探索を行う手法である。配列を個別に探索する場合、 ノイズのある二分探索 (noisy binary search) は配列要素の比較に確実性がない問題に対するアルゴリズムであり、各回の比較結果が一定の確率で誤っているにもかかわらず所定の正確さで目標値の位置を見つけ出すことができる。この種の手法はいずれも、平均して少なくとも 辞書ショートカット カテゴリ一覧 すべての辞書の索引
二分検索のページの著作権
ビジネス|業界用語|コンピュータ|電車|自動車・バイク|船|工学|建築・不動産|学問 ©2025 GRAS Group, Inc.RSS
|