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

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

探索アルゴリズム？

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

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

探索アルゴリズム

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

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

スポンサーリンク

線形探索（せんけいたんさく）

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

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

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

線形探索の流れ

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

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

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

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

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

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

2分探索（にぶんたんさく）

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

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

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

2分探索の流れ

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

まずは配列の中央位置を計算します。（最小位置：1、最大位置：8）

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

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

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

続いては位置1～3の中央位置を計算します。（最小位置：1、最大位置：3）

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

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

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

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

• 平均比較回数：(log₂n)回
• 最大比較回数：(log₂n)＋1回

スポンサーリンク

ハッシュ法

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

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

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

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

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

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

この問題は、設問のとおりハッシュ関数 mod(a₁＋a₂＋a₃＋a₄＋a₅，13) に54321をあてはめて計算し、配列のどの位置に入るか求めます。

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

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

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

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