アルゴリズムクイックリファレンス 第2版

5.1

 逐次探索

■

105

/**

力任せの逐次探索アルゴリズムを適用して、

*

（型

T

の）イテレータ処理可能な集まりから目標要素を探索する。

*/

public boolean sequentialSearch (Iterable<T> collection, T t) {

Iterator<T> iter = collection.iterator();

while (iter.hasNext()) {

if (iter.next().equals(t)) {

return true;

}

}

return false;

}

}

5.1.4

 分析

探索要素が集まりの中にあり、要素が見つかる確率がどの添字でも等しい（イテ

レータで取り出される場合には、どの位置でも等しい）場合には、

逐次探索

は平均

すると

n/2 + 1/2

個の要素を（

2

章「アルゴリズムの数学」で示したように）調べる。

すなわち、ほぼ半分の要素を調べ、

O(n)

性能ということだ。最良時は、探索要素が

集まりの先頭にあり、

O(1)

性能となる。このアルゴリズムは、平均時および最悪時

に線形時間かかる。集まりのサイズが

2

倍になると、探索に要する時間もほぼ

2

倍

になるはずだ。

逐次探索

の動作を示すために、範囲

[1, n ]

にある

n

個の整数の整列した集まりを

作った。集まりは整列されているのだが、探索コードはこの情報を使っていない。

100

回の試行を行った。各試行では、ランダムに選んだ目標値

t

の探索を

1000

回実

行した。

t

が見つかる確率は