[記事公開日]2015/01/31
[最終更新日]2016/11/29

基本情報技術者試験 2-7(データの探索)

探索イラスト

 

コンピュータ上で、

データの格納先を探す方法はいくつかあります。

 

・線形探索法(逐次探索法)

・2分探索法

・ハッシュ探索法

 


 

◆線形探索法(逐次探索法)

先頭から順にデータを探していきます。

 

「何回目でデータは探せるか?」

「平均でデータの数の半分の回数」です。

 

1番目から11番目までのデータがあれば、

「平均で6回目」です。

線形

●線形探索法(逐次探索法)

最少探索回数:1回

最大探索回数:N回

平均探索回数:(N+1)÷2回

 

※「N」というのはデータの数です。

※平均を計算するときに端数が生じることもあり

ますが、あくまでも平均のお話です。

 

●番兵法

線形探索法では「番兵法」と呼ばれる探索法があります。

単純に、データの最後に「番兵」を追加します。

※「番兵」とは、見張り番の兵士のことです。

 

「番兵」は探したいデータとイコールにしておきます。

つまり、「リンゴ」というデータを探したいときに、

最後のデータのさらに後ろに、「リンゴ」と番兵を置いておきます。

 

もし、最後の最後に検索したい値がヒットしたら、

それは番兵になります。

つまり、検索したい値は「無かった」と判断できます。

 

同じ「線形探索法」でも、

「番兵法」があるバージョンと、

「番兵法」がないバージョンがある

と理解してください。

 

具体的には、

番兵法を使うとアルゴリズムに、

「最後のデータまで検索したか?」

という質問を毎回しなくて済みます。

 

◆2分探索法

半分ずつ切り分けて検索していきます。

 

探したいデータが「1」~「100」のうち、

「20」だとします。

 

まず、「1+100÷2」をして、

真ん中の「50」(正確には50.5ですが)と

まず比較します。

 

「20」は「50」より値が小さいですから、

次は、その中央値を除いた「1~49」に

限定して調べます。2回目も中央値であ

る「1+49÷2=25」と比較します。

効率がいいですね。

 

※端数は除いてお考えください。

・端数を中央値ととる場合

・端数をカットする方法、

・あらかじめデータの母数に奇数なら「+1」をする・・

などといったやり方があります。

 

●2分探索法

平均探索回数:log2 N回

最大探索回数:log2(N+1)回

計算量:O(log2N)

 

※「log」という難しい言葉がでました。

数学用語ですが、

例えば、「log2 8」は3です。

「2」を3乗すると、「8」になります。

つまり、8個のデータからある値を探す

ときの平均探索回数は3回ということです。

2分探索(2)

 

2等分しながら探索していく訳ですから、

逆に、探索回数が1回増える度に、その2倍を

検索できることになります。

 

※8個のデータを、平均3回で検索できるとしたら、

16個のデータから検索するには、

平均4回の検索回数です。

 

◆ハッシュ探索法

あらかじめデータの格納場所を

ある計算式の答えにしておきます。

 

例えば、データ「99」の格納場所(アドレス)は、

「13」だったとします。

データ「99」を探そうと思ったときに、

「データの値÷5の余り+2」をします。

(答え:6)

この「÷5の余り+2」が”ある計算式”です。

 

計算はもっと複雑ですから、

一発でデータが格納されているアドレスに

辿り着くことができます。

 

ということで・・・

探索回数:1回

探索量:0(1)

です。

 

たまたま、計算結果が同じになることが

あります。

「99÷5の余り+2」と、

「104÷5の余り+2」の答えは

一緒ですよね。

 

この現象を「シノニム」といいます。

 

シノニムが発生した際は、

どちらかのアドレスを変更しなくてはいけません。。

 

どう変更するかは出題されませんのでご安心を!