2分探索とは？にぶんたんさく
2分探索とは、整列済みの列に対し、中央の要素と目的の値を比べて探索範囲を毎回半分ずつ捨てていく探索法。1回の比較で候補が半減するため、n件でおよそlog2(n)回、100万件でも20回程度で決着する。線形探索のO(n)に対しO(log n)。
最終更新：2026-10-06
この語が出る過去問を解く →背景
対象が大きくなるほど、先頭から順に見る方法は現実的でなくなる。ただし「半分に絞れる」ためには列が順序どおり並んでいることが前提で、つまり整列というコストを先払いして探索を安くする取引になっている。何度も検索するなら元が取れ、一度きりなら損をする——この費用対効果の判断が設計判断として問われる。
具体例
紙の辞書を真ん中から開いて前か後ろかを判断する動作がそのまま2分探索にあたる。データベースの索引に使われるB木も、1回の比較で探索範囲を大きく削るという同じ発想を多分岐へ広げたもの。
試験での引っ掛け
前提は「整列済み」であること。未整列なら整列コストを含めて比較する必要があり、1回しか探さない用途では線形探索が有利なこともある。範囲更新を中央±1にしないと無限ループになり、比較回数の切り上げ・切り捨てを取り違えると計算問題を落とす。
関連用語
出た過去問
出典：平成30年度 秋期 応用情報技術者試験 午前 問8（IPA）
探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
正解：ア：a=2分探索，b=線形探索，c=ハッシュ表探索
要点：整列順は2分探索、頻度順は線形探索、計算位置はハッシュ表探索。
探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。
出典：平成31年度 春期 応用情報技術者試験 午前 問5（IPA）
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズ…
正解：空き領域の大きさをキーとする2分探索木
要点：最適適合は大きさをキーとする探索木でO(log n)になる
最適適合では「要求量以上で最小の空き領域」を探すので、大きさをキーとした2分探索木に空き領域を格納しておけば、要求量以上の最小要素を木の高さ、すなわち平均O(log n)で見つけられる。線形リストやビットマップは先頭から順に走査する必要があり平均O(n)かかる。
出典：令和5年度 春期 応用情報技術者試験 午前 問5（IPA）
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズ…
正解：空き領域の大きさをキーとする2分探索木
要点：探索キーは検索条件に合わせる。大きさ順の木で最適適合が高速
最適適合では「要求量以上で最小の空き領域」を探す必要がある。空き領域の大きさをキーとする2分探索木にしておけば、根から要求量と比較しながら降りるだけで条件を満たす最小の領域が対数時間で見つかる。線形リストや全走査を伴う構造では領域数に比例した時間がかかる。
出典：令和6年度 秋期 応用情報技術者試験 午前 問5（IPA）
次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。
正解：13
要点：削除位置には左部分木の最大値か右部分木の最小値を移す
2分探索木でノードを削除し、その位置に1つの要素を移して木の性質を保つには、削除ノードの直前の値（左部分木の最大値）か直後の値（右部分木の最小値）を移す必要がある。削除対象12の右部分木は14を根とし、その左の子13が最小値なので、13を移せば左部分木の値はすべて13未満、右部分木はすべて13より大きいという条件が保たれる。
出典：令和7年度 春期 応用情報技術者試験 午前 問6（IPA）
図の2分探索木に1と0の二つの要素を順に追加したAVL木として，適切なものはどれか。
正解：根5、左の子3（左の子1（左の子0、右の子2）、右の子4）、右の子7（左の子6）
要点：AVL木は高さの差が2になった節点で回転し、平衡を回復する
AVL木は各節点で左右部分木の高さの差を1以内に保つ平衡2分探索木である。まず1を追加しても各節点の高さの差は1以内に収まるため回転は起きないが、続けて0を追加すると2を根とする部分木で左に偏り高さの差が2になる。左の左に偏った形なので1を軸に右回転し、1が親、0と2がその左右の子になる。結果として根5の左部分木が「1を親に0と2」を左にもつ形へ整い、他の部分は変わらない。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。