基本情報技術者

【基本情報技術者試験】探索アルゴリズム

本日のテーマは探索アルゴリズムです。
探索アルゴリズム?

問題

10進法で5桁のa1a2a3a4a5をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1+a2+a3+a4+a5,13) とし,求めたハッシュ値に対応する位置の配列要素に格納する場合,54321は次の配列のどの位置に入るか。ここで,mod(x,13) は,xを13で割った余りとする。

配列

ア:1 イ:2 ウ:7 エ:11

基本情報技術者令和元年秋期 午前問10 ※図は過去問を参考に作成したものです。

問題

2分探索に関する記述のうち,適切なものはどれか。

  • ア:2分探索するデータ列は整列されている必要がある。
  • イ:2分探索は線形探索より常に速く探索できる。
  • ウ:2分探索は探索をデータ列の先頭から開始する。
  • エ:n個のデータの探索に要する比較回数は,nlog2nに比例する。

基本情報技術者平成26年秋期 午前問6

基本情報技術者試験や応用情報技術者試験で出題される探索アルゴリズムの問題、探索アルゴリズムには「線形探索」「2分探索」「ハッシュ法」などがあり、過去問では「線形探索」「2分探索」「ハッシュ法」がどのような動きをするか問われる問題が出題されています。

本記事では、探索アルゴリズムについて図解を利用して分かりやすく解説しています。

本記事で学べること

  • 探索アルゴリズムについて理解する
  • 線形探索2分探索ハッシュ法の動きを理解する
  • 基本情報技術者試験の過去問の解き方を学ぶ

探索アルゴリズム

探索アルゴリズムとは、配列のような複数のデータが格納されている箱の中から目的のデータを探しだすアルゴリズムのことです。

基本情報技術者試験で主に出題される探索アルゴリズムには「線形探索」「2分探索」「ハッシュ法」があります。

スポンサーリンク

線形探索(せんけいたんさく)

線形探索は非常にシンプルな探索アルゴリズムであり、目的のデータを先頭から順に探索していく手法です

先頭から順に探索していき、目的のデータが見つかる もしくは 配列のデータをすべて確認したら線形探索は終了です。

それでは次の配列を用いて、線形探索の動きを説明していきます。

探索のアルゴリズム

線形探索の流れ

線形探索は目的のデータを先頭から順に探索していく手法です。そのため先頭の要素から順番に確認してきます。

先頭の要素は「7」なので「7」と「2」を比較します。目的のデータではないので次へ

最初の要素「7」と比較

続いて次の要素「1」と「2」を比較します。目的のデータではないので次へ

次の要素「1」と比較

続いて次の要素「3」と「2」を比較します。目的のデータではないので次へ

次の要素「3」と比較

続いて次の要素「8」と「2」を比較します。目的のデータではないので次へ

次の要素「8」と比較

続いて次の要素「2」と「2」を比較します。目的のデータがあったので線形探索を終了します。

次の要素「2」と比較

暗記メモ

  • 線形探索は先頭から順に目的のデータを探索するアルゴリズム

2分探索(にぶんたんさく)

2分探索は「昇順」または「降順」に並んでいる配列やリストに対して探索を行う手法です。

探索対象を1/2ずつ削り落としていくので効率よく探索することができます。

それでは次の配列を用いて、2分探索の動きを説明していきます。

二分探索開始

2分探索の流れ

2分探索は探索対象を1/2ずつ削り落としていく手法です。整列された配列の中央位置のデータと目的のデータを比較して、探索範囲を半分に絞り込んでいきます。

まずは配列の中央位置を計算します。(最小位置:1、最大位置:8)

中央位置の計算方法は次のとおり。

最小位置 + (最大位置 - 最小位置) / 2

今回の例の最小位置は「1」、最大位置は「8」なので「1 + (8 - 1) / 2 = 4」と中央位置を求めます。

計算した結果、配列の中央位置は「4」なので、位置4のデータ「7」と「6」比較します。比較した結果「6」の方が小さいので、探索の範囲を左半分に絞り込みます

2分探索手順1

続いては位置1~3の中央位置を計算します。(最小位置:1、最大位置:3)

今回の例の最小位置は「1」、最大位置は「3」なので「1 + (3 - 1) / 2 = 2」と中央位置を求めます。

計算した結果、配列の中央位置は「2」なので、位置2のデータ「3」と「6」を比較します。比較した結果「6」の方が大きいので、探索の範囲を右半分に絞り込みます。

2分探索手順2

最後に「6」と比較、「6」を見つけることができたので探索終了です。

位置3のデータ「6」と比較

暗記メモ

  • 2分探索は探索範囲を1/2に狭めることを繰り返して目的のデータを探索するアルゴリズム

基本情報技術者試験では2分探索の平均比較回数と最大比較回数の式を問われる問題が出題されることもあります。式は次のとおりです。

  • 平均比較回数:(log2n)回
  • 最大比較回数:(log2n)+1回

スポンサーリンク

ハッシュ法

ハッシュ法とは、一定の計算式(ハッシュ関数)を用いてデータの格納位置(格納アドレス)を特定する手法です。

例えば、一定の計算式を「mod(x, 10) 」とし「12」を配列に格納すると、次のように位置「2」の場所に格納されます。

※modは余りが返ってくる関数であり、mod(x, 10)は、xを10で割ったときの余りが返ってくる

ハッシュ法を用いてデータを格納

ハッシュ法を使って目的のデータを探索するときも格納したときと同じ計算式「mod(x, 10)」を使い、格納位置を特定します。

ハッシュ法で12を探索

暗記メモ

  • ハッシュ法は一定の計算式を用いてデータの格納位置を特定する手法
  • 線形探索法や2分探索法とは異なり、常に一定の時間(探索回数1回)で目的のデータを探索することができる

基本情報技術者試験 過去問の解説

基本情報技術者令和元年秋期 午前問10

問題

10進法で5桁のa1a2a3a4a5をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1+a2+a3+a4+a5,13) とし,求めたハッシュ値に対応する位置の配列要素に格納する場合,54321は次の配列のどの位置に入るか。ここで,mod(x,13) は,xを13で割った余りとする。

配列

ア:1 イ:2 ウ:7 エ:11

基本情報技術者令和元年秋期 午前問10

この問題は、設問のとおりハッシュ関数 mod(a1+a2+a3+a4+a5,13) に54321をあてはめて計算し、配列のどの位置に入るか求めます。

mod(5+4+3+2+1,13) = mod(15, 13) = 2

※15÷13の余りは2

ハッシュ法で計算した結果、格納位置は2となり「イ」が正解です。

基本情報技術者平成26年秋期 午前問6

問題

2分探索に関する記述のうち,適切なものはどれか。

  • ア:2分探索するデータ列は整列されている必要がある。
  • イ:2分探索は線形探索より常に速く探索できる。
  • ウ:2分探索は探索をデータ列の先頭から開始する。
  • エ:n個のデータの探索に要する比較回数は,nlog2nに比例する。

基本情報技術者平成26年秋期 午前問6

2分探索とは「昇順」または「降順」に並んでいる配列に対して探索範囲を半分に狭めることを繰り返して目的のデータを探索するアルゴリズムです。

解答ア

ア:2分探索するデータ列は整列されている必要がある。

→ 2分探索を行うにはデータが整列されていることが条件なので正解です。

解答イ

イ:2分探索は線形探索より常に速く探索できる。

→ 2分探索は線形探索よりも効率よく目的のデータを見つけることができるが、目的のデータが先頭にある場合は線形探索の方が早く処理ができるため不正解です。

解答ウ

ウ:2分探索は探索をデータ列の先頭から開始する。

→ 探索をデータ列の先頭から開始するのは、線形探索なので不正解です。

解答エ

エ:n個のデータの探索に要する比較回数は,nlog2nに比例する。

→ 2分探索の平均比較回数を求める式は log2n なので不正解です。

2分探索の説明をしているのは「ア」です。


チャンネル登録はこちら

フォローはこちら