線形探索と2分探索
配列に格納されているデータを探索するときの,探索アルゴリズムに関する記述のうち,適切なものはどれか。
- A
2分探索法は,探索対象となる配列の先頭の要素から順に探索する。
- B
線形探索法で探索するのに必要な計算量は,探索対象となる配列の要素数に比例する。
- C
線形探索法を用いるためには,探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- D
探索対象となる配列が同一であれば,探索に必要な計算量は探索する値によらず,2分探索法が線形探索法よりも少ない。
正解と解説を見る
正解:B
線形探索法の計算量は要素数に比例します(O(n))。2分探索法はO(log n)ですが、整列済みであることが前提です。
出典: 令和5年度 ITパスポート試験 公開問題 問69(IPA 独立行政法人情報処理推進機構)。解説はこのサイトが作成。
- A
誤り。先頭から順に探すのは線形探索法です。2分探索法は、整列済みの配列の中央の要素と比べ、探索範囲を半分ずつ絞り込みます。
- B
正しい。線形探索法は、最悪の場合に全要素を順に調べます。そのため、計算量は要素数nに比例します(O(n))。
- C
誤り。ソート(整列)済みであることが前提になるのは、2分探索法です。線形探索法は、未整列の配列にも使えます。
- D
誤り。探す値が先頭にあれば、線形探索法は1回の比較で終わります。探す値によっては線形探索法のほうが少なくなるので、「探す値によらず」常に少ないとはいえません。
このサイトの問題は、公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。独立行政法人情報処理推進機構(IPA)の公式サービスではありません。