分類テクノロジ系 » アルゴリズムとプログラミング » アルゴリズムとプログラミング新しい試験範囲外（2027年度からの新しい試験には出ない分野）年度令和5年度の100問の一覧
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
正解と解説
正解：イ
ア× 先頭の要素から順に探すのは線形探索法です。2分探索法は真ん中の要素と比べて、探す範囲を半分ずつに絞ります。
イ○ 正解 線形探索法は先頭から1つずつ比べるので、必要な比較の回数は要素数に比例して増えます。
ウ× 整列されている必要があるのは2分探索法のほうです。線形探索法は順にすべて見ていくので、並び順に関係なく使えます。
エ× 探す値が先頭にあれば、線形探索法は1回の比較で終わり、2分探索法より少なくなります。探す値によらず2分探索法が少ない、とは言えません。
解説
線形探索法は、配列の先頭から1つずつ順に比べていく方法です。並び順に関係なく使えますが、要素数が増えるとそれに比例して比べる回数が増えます。2分探索法は、昇順か降順に整列された配列で、真ん中の要素と比べて探す範囲を半分ずつに絞る方法です。比べる回数はおよそ log2 n 回で済みますが、整列済みであることが前提です。
線形探索法の計算量は要素数に比例し、2分探索法は半分ずつ絞るので要素数が増えても比較の回数がほとんど増えません。ただしこれは平均や最悪の場合の話で、毎回の探索で2分探索法が必ず少ないわけではありません。探す値が先頭にあると、次のように逆転します。
配列 {1, 3, 5, 7, 9, 11, 13} で 1 を探す
線形探索法：1 と比べて見つかる → 1回
2分探索法：7 と比べる → 3 と比べる → 1 と比べて見つかる → 3回
教科書 g37この問題の知識
アルゴリズムは問題を解くための手順で、順次・選択・繰返しの3つで組み立てます。流れ図と擬似言語の読み方、変数の値を書き出すトレース、空欄の埋め方、線形探索と2分探索、選択ソート・バブルソート・クイックソートと併合までを、公開問題を解ける形でまとめます。
Udemy の ITパスポート講座を、受講者数・★評価・口コミで比べたページです（広告を含みます）。
過去問教科書の一覧（現行の試験の順）教科書の一覧（新しい試験の順）
出典：IPA「ITパスポート試験 公開問題」令和5年度 問69。問題文と選択肢は改変せずに引用しています（表・図は文字に書き起こしたもの）。正解は IPA 公表の解答例によります。