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

104

■

5

章 探索

まりへの要素の頻繁な挿入は、動的配列管理を必要とする。これは、使用するプロ

グラミング言語が提供していることもあるが、そうでなければプログラマが自分で

注意する必要がある。どちらの場合も、要素を見つける期待時間は、

O(n)

であり、

要素の削除には、少なくとも

O(n)

の手間がかかる。

探索する要素の型について、

逐次探索

は制限が最も少ない。唯一の要件は、集ま

り中の任意の要素が探索目標の要素に合致しているかどうかを調べる関数が存在し

なければいけないことだ。この機能は、要素そのものに与えられていることが多い。

5.1.3

 解

逐次 探 索

の実装は、自明であることが多い。例 5-1に集まりを

逐次 探 索

する

Python

コードを示す。

例

5-1

 

Python

による逐次探索

def sequentialSearch(collection, t):

for e in collection:

if e == t:

return True

return False

コードはまったく単純だ。この関数は、集まり

collection

と探索目標

t

とを引数に

取る。集まりは、リストを含め

Python

のイテラブルなオブジェクトなら何でもよ

い。探索される要素は、演算子

==

を使って比較する。例5-2に

Java

で書き換えた

コードを示す。ジェネリッククラス

SequentialSearch

は、型引数

T

を取り、これは、

集まりの要素の型を指定する。このコードが正しく動くためには、

T

は、正当なメ

ソッド

equals(Object ...