昇順に整列された n個のデータが配列に格納されている。
探索したい値を2分探索法で探索するときの、おおよその比較回数を求める式はどれか。
| ア | log2n | イ | (log2n+1)/2 | ウ | n | エ | n2 |
答え ア
【解説】
2分探索法の比較回数はlog2nだから。
残念ながら、比較回数(オーダ)を試験の時の求めることは無理で、この問題は知識問題になります。
(答えを知っていたら自信を持って解答を書く、知らなかったら適当に解答を書く。以外はありません。)
各探索方法、ソート方法の比較回数(オーダ)を書きます。
【探索】
- 2分探索法:log2n
- ハッシュ探索:1
- 線形探索:n
- バブルソート:n2
- クイックソート:n log2n
- ヒープソート: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のデータに対し同様の探索を行う。 - 比較回数
コンピュータに行わせる多くの作業は、『データを探す(探索)』や『データを並び替える(整列、ソート)』で、これらの作業で最も時間のかかる処理は一般的に比較処理と考えられているため、比較回数の少ない方法(アルゴリズム)を用いることが時間の処理作業時間の短縮になると考えられている。
『データを探す』や『データを並び替える』の作業では使用する方法(アルゴリズム)によって比較回数がデータの母数(n)を使った式で表すことができこれをオーダ(O ( ))と呼ぶ。
もっと、「2分探索法」について調べてみよう。
戻る
一覧へ
次へ