「探索アルゴリズム」の解説 　〜ITパスポートR5年 問69〜

探索アルゴリズムとは、与えられた問題やデータセットから目的の情報を見つけ出すための手法や手順のことです。なお、線形探索と二分探索は一般的な探索アルゴリズムになります。

探索アルゴリズムとは？

探索とは、リストなどの中から必要なデータを探し出すこと。

線形探索法

線形探索アルゴリズムは、先頭のデータから順に、条件に照らし合わせながら調べていくアルゴリズムになります。シンプルで基本的な探索アルゴリズムと呼ばれています。単純ではありますが、探している値がデータベースの最後の要素であった場合、すべての要素を探索しなければいけないため手間がかかるデメリットがあります。

線形探索法の探索例

ここでは、[4,5,3,6,2,1]という並びのデータの中から3を探す場合を説明します。

1. まず、データの先頭の数字4と3が一致しているかを確認します。
2. 違う場合、次にデータの2つ目の数字5と3が一致しているかを確認します。
3. 3が出るまで繰り返します。

線形探索法の探索回数

探索対象のデータの母数Nに対し、線形探索では最大探索回数はN回、平均探索回数はN/2回になります。

二分探索法

二分探索アルゴリズムは、整列されたデータ群を2つのグループに分け、探索している要素がどちらのグループにあるかの判断を繰り返すことで、探索範囲を狭めていくアルゴリズムになります。

線形探索よりも効率的に探索を行うことができます。但し、データが整列されている必要があります。

整列されていないデータに対して、二分探索を行う場合は、ソートアルゴリズムを使って値を整列させてから二分探索を行います。

二分探索法の探索例

ここでは、[1,2,3,4,5,6]という並びのデータの中から3を探す場合を説明します。

1. まず、真ん中の数字4と3を比較します。※真ん中がない場合は１つ左側 or 右側を選びます。
2. 3のほうが小さいので、3はこれより左側に存在することがわかります。
3. 次に左側の3つのデータ[1,2,3]から真ん中の数字2と3を比較します。
4. 3のほうが大きいので、3はこれより右側に存在することがわかります。
5. 一つまで絞れたので3を3と比較します。

二分探索法の探索回数

二分探索の場合、最大探索回数は(log2N＋1)回、平均探索回数はlog2N回となります。
※ただし、あらかじめ大きい順または小さい順に整列されたデータである必要があります。

探索アルゴリズムに関する問題（令和5年問69）

配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。

   ア.  2分探索法は，探索対象となる配列の先頭の要素から順に探索する。

   イ.  線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。

   ウ.  線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。

   エ.  探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。

出典：令和5年度  ITパスポート試験公開問題 問69

正しいと思う選択肢をクリックしてみてください！！！