解答 イ
【頭の準備体操】
線形探索法は，配列の先頭の要素から順番に探す方法。
2分探索法は，探索範囲を半分に絞りながら探す方法。あらかじめデータは昇順又は降順にソートされている必要がある。
【イメージで解く】
データ5を探索する場合
線形探索法は5回。
※2分探索と比較するために，データはあらかじめ昇順に並べてある。
※赤枠は探索範囲。探索する値は探索範囲の中央とする。
- ア 線形探索法は,探索対象となる配列の先頭の要素から順に探索する。
- イ 正解
- ウ 2分探索法を用いるためには,探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ 探索対象となる配列が同一であれば,一般的に平均探索回数は2分探索法が線形探索法よりも少ない。ただし，探索する値(配列の先頭にあるときなど)によっては，線形探索の方が少ない場合もあり得る。
(参考)
配列の要素数がNのとき，
線形探索法の平均探索回数は，(N＋1)÷2回
2分探索法の平均探索回数は，log2N回