今回は、基本情報技術者試験でもよく出題されている『探索アルゴリズム』について、基本的な探索アルゴリズム4つとそれらに関する演習問題をご紹介していこうと思います。
インプットもアウトプットも同時に試せてしまうため、本記事を通して『探索アルゴリズム』に関する知識を確かなものにしてしまいましょう。
また、本記事で扱っている演習問題は、大半が基本情報技術者試験・応用情報技術者試験の過去問になるため、試験対策にもなります。
ぜひ最後まで見ていってください。
この記事でわかること
- 探索アルゴリズムについて
- 4つの探索アルゴリズムについて
- 探索アルゴリズムに対する演習問題
目次
用語解説
ではまず初めに、そもそも探索アルゴリズムって何？というところから、具体的に試験で出題されるような探索アルゴリズムを4つほど紹介していきます。
ちなみに、今回紹介する探索アルゴリズムは以下の4つです。
- 線形探索
- 2分探索
- ハッシュ法
- 文字列探索処理
それぞれについて以下で詳しく説明していきます。
探索アルゴリズムとは？
複数のデータで構成されているデータ列の中に、目的のデータが存在するかどうかを調べることを『探索』と呼び、探索のやり方のことを探索アルゴリズムと言います。
例えば、以下のような例を考えてみましょう。
人間が見れば一発で、データ列の中に目的のデータが入っていると判断できるのですが、コンピュータにはデータを探すための方法を教えてあげる必要があります。
その方法が、探索アルゴリズムというものになるので、以下で4つほど紹介していきますね。
①：線形探索
線形探索とは、データ列と目的のデータとの比較を、データ列の先頭の要素から順番に行うアルゴリズムのことです。
目的のデータがデータ列内にある場合は、一致した時点で探索終了。
目的のデータがデータ列内にない場合は、データ列の最後の要素と比較した後、探索終了といった感じです。
②：2分探索
2分探索とは、あらかじめ整列済みのデータ列の中から目的のデータを探すアルゴリズムのことです。
探索を行うデータ列が整列済みでないと、2分探索は行えないので注意しましょう。
上図は2分探索を行っている例になります。
2分探索では、線形探索よりも効率的に探索を行うために、まず初めに真ん中の要素と目的のデータを比較して、『真ん中の要素<目的のデータ』が成り立つならば、左半分のみを探索範囲として絞ります。
もちろん、『真ん中の要素>目的のデータ』でしたら、右半分を探索範囲にすればOKですね。
それを繰り返していき、線形探索よりも少ない比較回数で目的のデータを見つけます。
こちらの終了条件は、線形探索と同様に、目的のデータが見つかった時と最後まで探して見つからなかった時になります。
③：ハッシュ法
ハッシュ法とは、それぞれのデータに与えられている『キー』と呼ばれる値から、ハッシュ関数を用いて得たハッシュ値をもとにして、格納位置へとデータを格納する方法です。
言葉のみだとわかりにくいと思うので、図を用いて確認していきましょう。
ハッシュ法を使うとこのような形で、キーを用いてデータを指定の位置に格納することが出来ます。
なんでこんな面倒くさいデータ格納方法を使うの？
データを格納する場所なんて適当でよくない？
このように思う方も多いと思いますが、実はハッシュ法を用いてデータの格納を行うと、コンピュータが表とハッシュ関数を見るだけでデータがどこに格納されているのかを判断してくれます。
そのため、『線形探索』や『2分探索』と異なり、無駄な比較をする必要がないのです。
一発で要素を見つけることが出来るため、効率はめちゃくちゃ良いですね。
④：文字列探索処理
文字列探索処理は、ある文字列A内に文字列Bが入っているかどうかを探すためのアルゴリズムです。
ちなみに、ここでいう文字列とは、1文字以上の文字で構成されるデータのことです。
こちらも、図を見て確認していきましょう。
このように、1文字目から比較をしていき、文字列Aの中に文字列Bが存在するかどうかを調べます。
こちらももちろん、文字列が存在する場合はそれが判明した時点で、存在しない場合は最後まで比較を終えた時点で、探索終了ということになります。
演習問題
続いては基本情報技術者試験・応用情報技術者試験の過去問をもとにした演習問題です。
インプットした知識を演習を通じてアウトプットして、知識の定着を図りましょう。
演習問題①
探索表の構成法を例とともに a～c に示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
ア. a：2分探索 b：線形探索 c：ハッシュ探索
イ. a：2分探索 b：ハッシュ探索 c：線形探索
ウ. a：線形探索 b：2分探索 c：ハッシュ探索
エ. a：線形探索 b：ハッシュ探索 c：2分探索
演習問題②
昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，おおよその比較回数を求める式はどれか。
[基本情報技術者平成18年秋期 午前問14]
ア. log2n
イ. (log2n＋1)／2
ウ. n
エ. n2
演習問題③
2分探索に関する記述のうち，適切なものはどれか。
[基本情報技術者平成26年秋期 午前問6]
ア. 2分探索するデータ列は整列されている必要がある。
イ. 2分探索は線形探索より常に速く探索できる。
ウ. 2分探索は探索をデータ列の先頭から開始する。
エ. n個のデータの探索に要する比較回数は，nlog2nに比例する。
演習問題④
10進法で5桁の数 a1a2a3a4a5 をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1＋a2＋a3＋a4＋a5，13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321は配列のどの位置に入るか。ここで，mod(x，13) は，xを13で割った余りとする。
[基本情報技術者令和元年秋期 午前問10]
ア. 1
イ. 2
ウ. 7
エ. 11
演習問題⑤
配列Aの1番目からN番目の要素に整数が格納されている(N＞1)。次の図は，Xと同じ値が何番目の要素に格納されているかを調べる流れ図である。この流れ図の実行結果として，正しい記述はどれか。
ア. Xと同じ値が配列中にない場合，kには1が設定されている。
イ. Xと同じ値が配列中にない場合，kにはNが設定されている。
ウ. Xと同じ値が配列の1番目とN番目の2か所にある場合，kには1が設定されている。
エ. Xと同じ値が配列の1番目とN番目の2か所にある場合，kにはNが設定されている。
まとめ
今回は、以下の4つの探索アルゴリズムを紹介してきたのですが、いかがだったでしょうか。
| アルゴリズム名 | 説明 | 比較回数 |
|---|---|---|
| 線形探索 | 前から順番に探索を行う | (n+1)/2 |
| 2分探索 | 整列済みのデータから効率的に、探索を行う | log₂n |
| ハッシュ法 | ハッシュ関数を用いて、格納位置を一意に定める | 1 |
| 文字列探索処理 | 指定の文字列が、存在するかどうかを調べる | ー |
それぞれの特徴を抑えて、場面に合ったアルゴリズムを使用するようにしましょう。
また、基本情報技術者試験・応用情報技術者試験では、『整列アルゴリズム』とセットで出題されることが多いです。
整列アルゴリズムについてよくわからないといった方は、以下の記事を参考にしてみてください！
編集者のhitです！