2分探索に関する記述のうち、適切なものはどれか。
| ア | 2分探索するデータ列は整列されている必要がある。 |
| イ | 2分探索は線形探索より常に速く探索できる。 |
| ウ | 2分探索は探索をデータ列の先頭から開始する。 |
| エ | n 個のデータの探索に要する比較回数は、n log2n に比例する。 |
答え ア
【解説】
| ア | 2分探索では、データは整列されている必要があります。 |
| イ | 昇順に整列されたデータの最小値を探す時などは、線形探索法のほうが早くなります。 |
| ウ | 2分探索は探索をデータ列の真ん中から開始します。 |
| エ | 2分探索ハn 個のデータの探索に要する比較回数は、log2n に比例します。 |
【キーワード】
・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のデータに対し同様の探索を行う。
もっと、「2分探索」について調べてみよう。
戻る
一覧へ
次へ