正答2
解説
正解は2です。
線形探索法と2分探索法の特徴を問う問題です。
線形探索法は先頭から順に探し、2分探索法は整列済みの配列の中央と比べて範囲を半分ずつ絞り込みます。
【選択肢別解説】
1：× 先頭の要素から順に探索するのは線形探索法です。
2分探索法は、探索範囲の中央の要素から比較を始めます。
2：○ 線形探索法は1つずつ順に調べるので、平均の比較回数は要素数に比例して増えます。
要素数が2倍になれば、計算量もおよそ2倍になります。
3：× 線形探索法は、配列がソートされていなくても使えます。
ソート済みであることが必要なのは、2分探索法です。
4：× 探す値が先頭にある場合、線形探索法は1回の比較で見つかります。
探す値によっては線形探索法の方が少なく済むので、常に2分探索法が少ないとはいえません。
【ポイント】
平均比較回数は、線形探索法が要素数Nの約半分、2分探索法がlog₂N程度です。
要素数が多いほど2分探索法が有利ですが、事前の整列が必要です。