2-3. 線形探索法（逐次探索法）の平均比較回数
本記事では、線形探索法の平均比較回数を求めるアルゴリズムについて解説します。問題のレベルは、基本情報技術者試験レベルです。
なお、線形探索法は、リニアサーチとも呼ばれます。
問題 1, 000人の個人顧客名を並べた名簿がある。来客名による検索を線形探索法を用いて行う。平均比較回数の見積もりとして正しい組み合わせはどれか。
a: 名簿中に来客名がないとき、ないことが分かるまでの平均比較回数
b: 名簿中に来客名があるとき、その顧客名に到達するまでの平均比較回数
ア a: 333, b: 333
イ a: 500, b: 333
ウ a: 500, b: 500
エ a: 1,000 , b: 500
オ a: 1,000, b: 1,000
解説
線形探索とは、逐次探索のことです。顧客名は順に並んでいないので、先頭から順にひとつずつ探していき、最期の来客名と比較して一致しなかったときに、目的の顧客名が名簿になかったことが分かります。
したがって、名簿中に顧客名がないことがないことが分かるのは、1,000回の比較が終わった段階です。
一方、名簿中にある顧客名の場合、1回目に見つかる、2回目に見つかる‥、1,000回目に見つかると様々です。従って、その平均である500回というのが、平均比較回数になります。この平均比較回数は、アルゴリズムの効率を評価するために使われます。同じ個数のデータから探索するときには、平均比較回数が少ない方が効率が良いです。
補足1（シンプルに解説）
1. 名簿に顧客名がある場合の平均比較回数 (b)
名簿のどこにあるかはランダムと考えられます。1回目に見つかる可能性、2回目に見つかる可能性…と均等に分布しているとすると、
平均比較回数は
1+2+⋯+1000 /1000 = 500.5
したがって、およそ 500回 となります。
2. 名簿に顧客名がない場合の平均比較回数 (a)
顧客名が名簿にない場合、1,000回すべてを比較しないと名簿にないことが分かりません。
したがって、1,000回 となります。
補足2
線形探索（リニアサーチ）の基本例題
線形探索とは、配列やリストの要素を先頭から順に調べていき、目的の値を見つけるアルゴリズムです。
以下に、Java と Python で実装します。
Java の実装
public class LinearSearchExample {
public static int linearSearch(int[] arr, int target) {
int comparisons = 0;
for (int i = 0; i < arr.length; i++) {
comparisons++; // 比較回数をカウント
if (arr[i] == target) {
System.out.println("見つかりました: " + target + " (比較回数: " + comparisons + ")");
return i; // 見つかった場合はインデックスを返す
}
}
System.out.println("見つかりませんでした (比較回数: " + comparisons + ")");
return -1; // 見つからなかった場合
}
public static void main(String[] args) {
int[] data = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int target = 50;
linearSearch(data, target); // 配列内にある場合
int targetNotFound = 110;
linearSearch(data, targetNotFound); // 配列内にない場合
}
}
Java の出力例
見つかりました: 50 (比較回数: 5)
見つかりませんでした (比較回数: 10)
Python の実装
def linear_search(arr, target):
comparisons = 0
for i, value in enumerate(arr):
comparisons += 1 # 比較回数をカウント
if value == target:
print(f"見つかりました: {target} (比較回数: {comparisons})")
return i # 見つかった場合はインデックスを返す
print(f"見つかりませんでした (比較回数: {comparisons})")
return -1 # 見つからなかった場合
# 実行例
data = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target = 50
linear_search(data, target) # 配列内にある場合
target_not_found = 110
linear_search(data, target_not_found) # 配列内にない場合
Python の出力例
見つかりました: 50 (比較回数: 5)
見つかりませんでした (比較回数: 10)
アルゴリズムの考え方
配列の先頭から順番に探す
インデックス 0 から順に target と一致するかを比較する。
一致したら、そのインデックスを返す。
一致しなければ、次の要素を調べる。
すべての要素を調べても見つからない場合
配列の最後まで比較しても target が見つからなければ -1 を返す。
アルゴリズムの平均比較回数
探索対象が配列内にある場合：(n+1)/2 回（平均）
探索対象が配列内にない場合：n 回
この方法はシンプルですが、大量のデータを処理する場合は二分探索やハッシュ検索などより効率的なアルゴリズムが必要になります。
以上です。