2分探索とは？

2分探索の意味

昇順または降順に整列済みのデータに対し、中央の要素と比較して探索範囲を毎回半分に絞り込む方法。比較のたびに候補が半減するので、要素数 n に対しおよそ log2(n) 回の比較で済む。FEでは比較回数の見積りが頻出。

2分探索の具体例

1000件なら、1000→500→250→…と絞られるので最大10回程度の比較で決着する。100万件でも20回程度で、線形探索の平均50万回と比べると桁違いに少ない。

2分探索は試験でどう引っ掛けられる？

前提として「整列済み」が必須。未整列のデータには使えないため、1回しか探さないなら整列にかかる時間を含めると線形探索のほうが速いこともある。範囲の更新（中央＋1、中央−1）の境界も誤りやすい。

2分探索と関連する用語

• 線形探索
• 二分探索木（BST）
• 計算量とオーダ記法

2分探索が出た過去問

• 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。

  正解：ア：a=2分探索，b=線形探索，c=ハッシュ表探索

  要点：整列順は2分探索、頻度順は線形探索、計算位置はハッシュ表探索。

  探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問8（IPA）

• 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズ…

  正解：空き領域の大きさをキーとする2分探索木

  要点：最適適合は大きさをキーとする探索木でO(log n)になる

  最適適合では「要求量以上で最小の空き領域」を探すので、大きさをキーとした2分探索木に空き領域を格納しておけば、要求量以上の最小要素を木の高さ、すなわち平均O(log n)で見つけられる。線形リストやビットマップは先頭から順に走査する必要があり平均O(n)かかる。

  出典：令和1年度 春期 応用情報技術者試験 午前 問5（IPA）

• 要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズ…

  正解：空き領域の大きさをキーとする2分探索木

  要点：探索キーは検索条件に合わせる。大きさ順の木で最適適合が高速

  最適適合では「要求量以上で最小の空き領域」を探す必要がある。空き領域の大きさをキーとする2分探索木にしておけば、根から要求量と比較しながら降りるだけで条件を満たす最小の領域が対数時間で見つかる。線形リストや全走査を伴う構造では領域数に比例した時間がかかる。

  出典：令和5年度 春期 応用情報技術者試験 午前 問5（IPA）

• 次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。

  正解：13

  要点：削除位置には左部分木の最大値か右部分木の最小値を移す

  2分探索木でノードを削除し、その位置に1つの要素を移して木の性質を保つには、削除ノードの直前の値（左部分木の最大値）か直後の値（右部分木の最小値）を移す必要がある。削除対象12の右部分木は14を根とし、その左の子13が最小値なので、13を移せば左部分木の値はすべて13未満、右部分木はすべて13より大きいという条件が保たれる。

  出典：令和6年度 秋期 応用情報技術者試験 午前 問5（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」を左にもつ形へ整い、他の部分は変わらない。

  出典：令和7年度 春期 応用情報技術者試験 午前 問6（IPA）