IT PASSPORT
ITパスポートの問題解説
問題
整列済みのデータ1,000件に対して二分探索を行う。目的の値を見つけるまでに必要な比較回数は最悪でおよそ何回か。
- ア 約32回
- イ 約10回
- ウ 約500回
- エ 約1,000回
出典：オリジナル問題｜参考範囲：IPA ITパスポート試験シラバス（最新版）、情報処理技術者試験の基礎知識
正解と解説
正解：約10回
解説：二分探索は1回比較するたびに探索範囲を約半分に絞り込みます。1,000件を半分にしていくと500→250→125→63→…と進み、おおむね10回(2の10乗＝1,024)で範囲が1件まで縮まります。一般に件数Nに対する比較回数はlog₂Nに比例し、これが二分探索の計算量がO(log N)と表される理由です。線形探索なら最悪1,000回かかるところを約10回に抑えられるため、データ量が大きいほど効果が際立ちます。例えば件数がさらに10倍の1万件になっても比較回数は約14回程度にしか増えず、増え方が非常に緩やかなのが特長です。なお、二分探索を使う前提としてデータが整列済みである必要があります。誤答の約500回・約1,000回はいずれも線形探索の平均・最悪の回数で、半分ずつ絞る二分探索の見積もりとは別物です。
覚え方：「半分ずつ＝2を何回かけたら超えるか」で考えると速いです。2の10乗が約1,000と覚えておくと、1,000件なら約10回という見積もりが一瞬でできます。
他の選択肢はなぜ違う？
- ア約32回は1,000の平方根に近い値で、二分探索の比較回数の見積もりとは関係がありません。
- ウ約500回は線形探索で平均的に必要となる比較回数（全件の半分）であり、二分探索の値ではありません。
- エ約1,000回は線形探索で最悪全件を調べる場合の回数で、範囲を半分に絞る二分探索には当てはまりません。
この問題について
IPAのITパスポート試験シラバスとIT基礎知識を参考に、Sikaku Master向けに独自作成した問題です。公式試験問題・過去問題の転載ではありません。
IPAの過去問題の転載ではなく、シラバス・公開情報に基づく独自問題として作成しています。