コンピュータ上で、
データの格納先を探す方法はいくつかあります。
・線形探索法（逐次探索法）
・２分探索法
・ハッシュ探索法
◆線形探索法（逐次探索法）
先頭から順にデータを探していきます。
「何回目でデータは探せるか？」
⇒「平均でデータの数の半分の回数」です。
1番目から11番目までのデータがあれば、
「平均で6回目」です。
↓
●線形探索法（逐次探索法）
最少探索回数：1回
最大探索回数：Ｎ回
平均探索回数：(Ｎ＋1)÷２回
※「Ｎ」というのはデータの数です。
※平均を計算するときに端数が生じることもあり
ますが、あくまでも平均のお話です。
●番兵法
線形探索法では「番兵法」と呼ばれる探索法があります。
単純に、データの最後に「番兵」を追加します。
※「番兵」とは、見張り番の兵士のことです。
「番兵」は探したいデータとイコールにしておきます。
つまり、「リンゴ」というデータを探したいときに、
最後のデータのさらに後ろに、「リンゴ」と番兵を置いておきます。
もし、最後の最後に検索したい値がヒットしたら、
それは番兵になります。
つまり、検索したい値は「無かった」と判断できます。
同じ「線形探索法」でも、
「番兵法」があるバージョンと、
「番兵法」がないバージョンがある
と理解してください。
具体的には、
番兵法を使うとアルゴリズムに、
「最後のデータまで検索したか？」
という質問を毎回しなくて済みます。
◆2分探索法
半分ずつ切り分けて検索していきます。
探したいデータが「1」~「100」のうち、
「20」だとします。
まず、「1＋100÷2」をして、
真ん中の「50」（正確には50.5ですが）と
まず比較します。
「20」は「50」より値が小さいですから、
次は、その中央値を除いた「1～49」に
限定して調べます。2回目も中央値であ
る「1＋49÷2＝25」と比較します。
効率がいいですね。
※端数は除いてお考えください。
・端数を中央値ととる場合
・端数をカットする方法、
・あらかじめデータの母数に奇数なら「＋１」をする・・
などといったやり方があります。
●2分探索法
平均探索回数：log2 N回
最大探索回数：log2（N＋1）回
計算量：O（log2N）
※「log」という難しい言葉がでました。
数学用語ですが、
例えば、「log2 8」は３です。
↓
「2」を3乗すると、「8」になります。
つまり、8個のデータからある値を探す
ときの平均探索回数は3回ということです。
2等分しながら探索していく訳ですから、
逆に、探索回数が1回増える度に、その2倍を
検索できることになります。
※8個のデータを、平均3回で検索できるとしたら、
16個のデータから検索するには、
平均4回の検索回数です。
◆ハッシュ探索法
あらかじめデータの格納場所を
ある計算式の答えにしておきます。
例えば、データ「99」の格納場所（アドレス）は、
「13」だったとします。
↓
データ「99」を探そうと思ったときに、
「データの値÷５の余り＋２」をします。
（答え：6）
この「÷５の余り＋２」が”ある計算式”です。
計算はもっと複雑ですから、
一発でデータが格納されているアドレスに
辿り着くことができます。
ということで・・・
探索回数：１回
探索量：0（1）
です。
たまたま、計算結果が同じになることが
あります。
「99÷５の余り＋2」と、
「104÷５の余り＋2」の答えは
一緒ですよね。
この現象を「シノニム」といいます。
シノニムが発生した際は、
どちらかのアドレスを変更しなくてはいけません。。
どう変更するかは出題されませんのでご安心を！
