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

5.1

 逐次探索

■

103

序は重要ではない。集まり

C

の要素が

SQL

文で使うデータベース・カーソルのよう

に

C

から要素を

1

つずつ取り出す読み取り専用のイテレータによってしか得られな

いこともある。本章では添字を使うアクセス方式も含めて示す。

逐次探索

Sequential Search

最良 平均 最悪

O(1) O(n)

search (A,t)

for i=0 to n-1 do

❶

位置

0

から

n-1

まで、各要素に順にアクセスする。

if A[i] = t then

return true

return false

end

search (C,t)

iter = C.begin()

while iter

≠

C.end() do

❷

イテレータは、要素が尽きるまで続ける。

e = iter.next()

❸

各要素は、イテレータにより

1

つずつ取り出される。

if e = t then

return true

return false

end

5.1.1

 入出力

入力は、要素数が

n

＞

0

の集まり

C

と、探索する目標値

t

からなる。探索は、

t

が

C

の中にあれば、

true

を返し、そうでないと

false

を返す。

5.1.2

 文脈

集まりは整列していてもよいし、していなくてもよい。その集まりのある要素を

頻繁に探す必要が生じたとする。集まりについての情報が他にないので、

逐次探

索

で力任せに処理する。集まりに対して、一度に

1

つずつ要素を返すイテレータ

（

iterator

、反復子）しかない場合には、

逐次探索

だけが利