アルゴリズムとプログラミング｜令和5年度 ITパスポート試験 問69

• 2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
• ✓ これが正解線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
• 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
• 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。

解説

線形探索法にかかる手間は、配列の要素数に比例します。

線形探索法は、配列の先頭から順に一つずつ見ていき、探している値と同じものが見つかるまで進む方法です。最悪の場合は最後まで見ることになるので、必要な手間は要素数に比例して増えます。これに対し2分探索法は、並び替えてある配列の真ん中と比べて、探す範囲を半分ずつ絞っていく方法です。手間は要素数の増え方に比べてずっと緩やかにしか増えませんが、あらかじめ並び替えてあることが前提になります。どちらが有利かは、探す回数と並び替えの手間を合わせて考えることになります。よって適切なのは、線形探索法で探索するのに必要な計算量は、配列の要素数に比例する、という記述です。

ほかの選択肢はなぜ違うのか

• 先頭の要素から順に探索するのは線形探索法のほうです。2分探索法は真ん中と比べて範囲を半分ずつ絞るので、先頭から順に見ていくことはありません。二つの方法の説明が入れ替わっています。あらかじめ並べ替えてあることが前提になるのも、2分探索法のほうです。
• 並び替えられている必要があるのは2分探索法のほうです。線形探索法は先頭から順に見るだけなので、並びがばらばらでも使えます。むしろ並び替えの手間が要らない点が、この方法の取りえです。
• 探索する値によらず常に2分探索法のほうが少ない、とは言えません。探している値がたまたま配列の先頭にあれば、線形探索法は一度比べるだけで済みます。平均や最悪の場合の話と、個々の場合の話は区別が要ります。

この問題に関係する言葉

• 線形探索
• 配列
• 計算量

出典：令和5年度 ITパスポート試験 問69

この問題を演習で解く

同じ単元をまとめて解くならアルゴリズムとプログラミングへ。

この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）