2分探索とは？にぶんたんさく
2分探索とは、整列済みのデータの真ん中の値と目的の値を比べ、探す範囲を毎回半分に捨てていく探索方法。n件なら比較はおよそ log2(n) 回（2を何回掛けるとnになるかの回数）で済み、100万件でも20回程度で見つかる。先頭から順に見る線形探索より速いが、データが昇順か降順に並んでいることが使う前提になる。
最終更新：2026-10-09
この語が出る過去問を解く →背景
線形探索は件数が2倍になれば時間も2倍になるため、扱うデータが増えるほど待ち時間がそのまま伸びる。整列されているという条件を1つ足すだけで、1回の比較で候補を半分捨てられるようになり、件数が増えても比較回数はほとんど増えなくなる。基本情報では科目Bの擬似言語のトレース（変数の値の変化を表で追うこと）と、計算量（データが増えたときの処理時間の伸び方）の比較の両方で出る。
具体例
1,000件の整列済みの名簿から目的の番号を探すなら、まず真ん中の500番目と比べて前半か後半の500件に絞り、次は250件、125件…と半分ずつ減らしていく。1,000→500→250→…と絞られるので、最大10回程度の比較で決着する。
試験での引っ掛け
未整列のデータには使えない。1回しか探さないなら、整列にかかる時間を含めると線形探索のほうが速いこともある。範囲を狭めるときの更新（中央の1つ右／1つ左）を間違えると、目的の値をまたいで無限に回る。
関連用語
出た過去問
問題文で直接問われたものと、解説の中で触れられたものが含まれます。
出典：平成28年度 秋期 基本情報技術者試験 午前 問6（IPA）
2分探索木になっている2分木はどれか。
正解：根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。
要点：2分探索木は左部分木＜節点＜右部分木が全節点で成立
2分探索木は、任意の節点について左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きいという条件を満たす木である。根17に対し左側が10・14・16、右側が18・19となり、さらに14の左が10・右が16、19の左が18と、どの節点でも条件が崩れていない木が正解となる。
出典：平成28年度 春期 基本情報技術者試験 午前 問5（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となる。
出典：平成29年度 春期 基本情報技術者試験 午前 問7（IPA）
顧客番号をキーとして顧客データを検索する場合，2分探索を使用するのが適しているものはどれか。
正解：顧客番号の昇順に配置されているデータ構造
要点：2分探索の前提はデータがキー順に整列していること
2分探索は探索範囲の中央の値と目的のキーを比べ、大小関係から探索範囲を半分に絞り込む手法です。この絞り込みが成り立つのは、データがキーの順に並んでいる場合に限られます。したがって顧客番号の昇順に配置されたデータ構造が適します。
出典：平成31年度 春期 基本情報技術者試験 午前 問5（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と、どのノードでも条件が崩れていない。
出典：令和4年度 公開問題 基本情報技術者試験 科目A 問5（IPA）
2分探索木になっている2分木はどれか。
正解：イ：根17、左の子14（さらに左10・右16）、右の子19（さらに左18）
要点：2分探索木は全節点で左部分木＜節点＜右部分木が成立する
2分探索木は、任意の節点について左部分木の全要素がその節点より小さく、右部分木の全要素が大きいという条件を満たす木である。各木で節点ごとにこの大小関係を確認すると、条件を崩す節点が無いものは1つだけである。根より小さい値が右側にある、あるいは左の子より大きい値が左部分木にあるといった違反があれば2分探索木ではない。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。