2分探索とは？

2分探索の意味

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

2分探索の具体例

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

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

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

2分探索と関連する用語

• 線形探索
• 2分探索木
• 計算量とオーダ記法

2分探索が出た過去問

• 2分探索木になっている2分木はどれか。

  正解：根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。

  要点：2分探索木は左部分木＜節点＜右部分木が全節点で成立

  2分探索木は、任意の節点について左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きいという条件を満たす木である。根17に対し左側が10・14・16、右側が18・19となり、さらに14の左が10・右が16、19の左が18と、どの節点でも条件が崩れていない木が正解となる。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問6（IPA）

• 10個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振…

  正解：a＝6，b＝7

  要点：2分探索木は左→節→右の順に走査すると値が昇順に並ぶ

  この条件は2分探索木の性質そのもので、木を左から順に（左部分木→自分→右部分木の順に）たどると値が1から10まで昇順に並ぶ。根が5なので左部分木の4個の節に1〜4、右部分木の5個の節に6〜10が入る。右部分木はaに左の子が無く右の子をもつ形なので、その順序ではaが最初に来て6、次にaの右の子の左の子であるbが7となる。

  出典：平成28年度 春期 基本情報技術者試験 午前 問5（IPA）

• 顧客番号をキーとして顧客データを検索する場合，2分探索を使用するのが適しているものはどれか。

  正解：顧客番号の昇順に配置されているデータ構造

  要点：2分探索の前提はデータがキー順に整列していること

  2分探索は探索範囲の中央の値と目的のキーを比べ、大小関係から探索範囲を半分に絞り込む手法です。この絞り込みが成り立つのは、データがキーの順に並んでいる場合に限られます。したがって顧客番号の昇順に配置されたデータ構造が適します。

  出典：平成29年度 春期 基本情報技術者試験 午前 問7（IPA）

• 2分探索木として適切なものはどれか。ここで、数字1〜9は、各ノード（節）の値を表す。

  正解：イ：根が4、左の子が2（さらに左の子1・右の子3）、右の子が8（さらに左の子6・右の子9、6の左の子5・右の子7）の木

  要点：2分探索木は全ノードで左＜自分＜右が成り立つ木

  2分探索木は、任意のノードについて左部分木の全値がそのノードより小さく、右部分木の全値が大きいという条件を満たす木である。イは根が4で、左部分木が1・2・3のみ、右部分木が5〜9のみとなっている。さらに部分木の内部でも、2の左が1・右が3、8の左が6（その左5・右7）・右が9と、どのノードでも条件が崩れていない。

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

• 2分探索木になっている2分木はどれか。

  正解：イ：根17、左の子14（さらに左10・右16）、右の子19（さらに左18）

  要点：2分探索木は全節点で左部分木＜節点＜右部分木が成立する

  2分探索木は、任意の節点について左部分木の全要素がその節点より小さく、右部分木の全要素が大きいという条件を満たす木である。各木で節点ごとにこの大小関係を確認すると、条件を崩す節点が無いものは1つだけである。根より小さい値が右側にある、あるいは左の子より大きい値が左部分木にあるといった違反があれば2分探索木ではない。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問5（IPA）