令和5年度 ITパスポート 問69（テクノロジ）
出典：令和5年度 ITパスポート試験 公開問題 問69（独立行政法人情報処理推進機構（IPA））
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
- ア2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
正解と解説を見る
正解：イ
【線形探索法と2分探索法】
・線形探索法：配列の先頭から順に1つずつ調べていく方法です。データが並べ替えられていなくても使えます。調べる回数は、最悪で要素数と同じになるので、計算量は要素数に比例します
・2分探索法：データを昇順や降順に並べ替えておき、探索範囲の真ん中の要素と比べて、探す値がその前半にあるか後半にあるかを判断し、範囲を半分ずつに絞り込んでいく方法です。要素数が多いほど、線形探索法より大幅に少ない回数で見つけられます
【選択肢の検討】
ア：先頭から順に探索するのは、線形探索法です。2分探索法は、真ん中の要素から調べます。
イ：線形探索法の計算量は、要素数に比例するので、適切です。
ウ：並べ替えが必要なのは2分探索法で、線形探索法は並べ替えなしで使えます。
エ：探す値によって計算量は変わります。例えば、探す値が先頭にあれば、線形探索法は1回で見つけられ、2分探索法より少なくて済みます。
よって、正解は選択肢イです。