平成26年秋期基本情報技術者午前問6

平成26年秋期基本情報技術者午前問6

2分探索に関する記述のうち、適切なものはどれか。

ア	2分探索するデータ列は整列されている必要がある。
イ	2分探索は線形探索より常に速く探索できる。
ウ	2分探索は探索をデータ列の先頭から開始する。
エ	n 個のデータの探索に要する比較回数は、n log₂n に比例する。

【キーワード】
・2分探索法

【キーワードの解説】

2分探索法
整列されたデータ内から、目的のデータを探す方法。
「整列された」とは大きい順(降順)や、小さい順(昇順)にデータが並んでいる状態になっていること。
2分探索法について例を示しながら説明する。探す対象となるデータが1…Nの順で昇順の場合、まず(1+N)/2番目のデータと目的のデータの大小を比較する。
(1+N)/2番目のデータが探しているデータの場合、
　探索終了。
(1+N)/2番目のデータが探しているデータより小さい場合、
　1…((1+N)/2-1)のデータに対し同様の探索を行う。
(1+N)/2番目のデータが探しているデータより大きい場合、
　((1+N)/2+1)…Nのデータに対し同様の探索を行う。

戻る一覧へ次へ