線形探索せんけいたんさく

1導入どうにゅう

この講義こうぎでは、配列はいれつを先頭せんとうから順じゅんに比較ひかくする線形探索せんけいたんさくについて、処理手順しょりてじゅん、正当性せいとうせい、計算量けいさんりょうを説明せつめいする。任意にんいの配列はいれつに対たいして等値比較とうちひかくだけを使用しようし、整列せいれつや補助的ほじょてきな検索構造けんさくこうぞうを仮定かていしない場合ばあい、ある要素ようそとの比較結果ひかくけっかから他ほかの要素ようそを一括いっかつして除外じょがいすることはできない。このため、各要素かくようそを個別こべつに検査けんさする方法ほうほうが基本きほんとなる。

2問題設定もんだいせっていと用語ようご

長ながさ $$n$$n の配列はいれつ

と目標値もくひょうち $$x$$x を入力にゅうりょくとする。添字そえじ $$i$$i が $$A_i=x$$A_i=x を満みたすなら、そのような添字そえじのうち最小さいしょうのものを返かえす。該当がいとうする添字そえじが存在そんざいしないなら、探索失敗たんさくしっぱいを返かえす。

線形探索せんけいたんさくLinear searchとは、$$A_0,A_1,\dots ,A_{n-1}$$A_0,A_1,\ldots,A_{n-1} をこの順序じゅんじょで目標値もくひょうちと比較ひかくし、最初さいしょの一致いっちで終了しゅうりょうする探索法たんさくほうである。比較回数ひかくかいすうNumber of comparisonsとは、等式とうしき $$A_i=x$$A_i=x を判定はんていした回数かいすうである。

3処理手順しょりてじゅん

$$i=0,1,\dots ,n-1$$i=0,1,\ldots,n-1 の順じゅんに、次つぎの処理しょりを実行じっこうする。

1. $$A_i=x$$A_i=x を判定はんていする。
2. 等式とうしきが成立せいりつするなら $$i$$i を返かえして終了しゅうりょうする。
3. 等式とうしきが成立せいりつしないなら、次つぎの添字そえじへ移行いこうする。

すべての添字そえじにおいて一致いっちしなければ、探索失敗たんさくしっぱいを返かえす。この手順てじゅんは配列はいれつの整列状態せいれつじょうたいに依存いぞんしない。

4不変条件ふへんじょうけんによる正当性せいとうせい

ループ不変条件ふへんじょうけんLoop invariantとは、反復処理はんぷくしょりの所定しょていの時点じてんで常つねに成立せいりつする命題めいだいである。添字そえじ $$i$$i の比較直前ひかくちょくぜんに、次つぎの不変条件ふへんじょうけんを設定せっていする。

不変条件ふへんじょうけんは「$$A_0,A_1,\dots ,A_{i-1}$$A_0,A_1,\ldots,A_{i-1} のいずれも $$x$$x と一致いっちしない」である。

4.1初期化しょきか

最初さいしょの比較直前ひかくちょくぜんでは $$i=0$$i=0 である。既すでに比較ひかくした要素ようそは存在そんざいしないため、空くうの添字集合そえじしゅうごうに対たいして不変条件ふへんじょうけんが成立せいりつする。

4.2保存ほぞん

添字そえじ $$i$$i の比較直前ひかくちょくぜんに不変条件ふへんじょうけんが成立せいりつすると仮定かていする。$$A_i=x$$A_i=x なら、$$i$$i より小ちいさい添字そえじでは一致いっちしないため、$$i$$i は条件じょうけんを満みたす最小さいしょうの添字そえじである。$$A_i\ne x$$A_i\ne x なら、既検査部分きけんさぶぶん $$A_0,\dots ,A_i$$A_0,\ldots,A_i のいずれも $$x$$x と一致いっちしない。したがって、$$i+1$$i+1 の比較直前ひかくちょくぜんにも不変条件ふへんじょうけんが成立せいりつする。

4.3終了しゅうりょう

一致いっちによって終了しゅうりょうする場合ばあい、保存ほぞんの議論ぎろんにより、返却へんきゃくする添字そえじは最初さいしょの一致位置いっちいちである。一致いっちせずに $$i=n$$i=n へ到達とうたつする場合ばあい、不変条件ふへんじょうけんから $$A_0,\dots ,A_{n-1}$$A_0,\ldots,A_{n-1} のいずれも $$x$$x と一致いっちしない。ゆえに、探索失敗たんさくしっぱいという返却結果へんきゃくけっかは正ただしい。

初期化しょきか、保存ほぞん、終了しゅうりょうの三段階さんだんかいにより、線形探索せんけいたんさくは仕様しようを満みたす。

5計算量けいさんりょう

$$n>0$$n>0 とする。目標値もくひょうちが先頭要素せんとうようそ $$A_0$$A_0 と一致いっちする最良さいりょうの場合ばあい、比較回数ひかくかいすうは $$1$$1 であり、時間計算量じかんけいさんりょうは $$\mathrm{\Theta }\left(1\right)$$\Theta(1) である。

目標値もくひょうちが末尾要素まつびようそとのみ一致いっちする場合ばあい、または配列内はいれつないに存在そんざいしない場合ばあい、比較回数ひかくかいすうは $$n$$n である。したがって、最悪時間計算量さいあくじかんけいさんりょうは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) である。ループの添字そえじと返却値へんきゃくちを除のぞいて入力長にゅうりょくちょうに比例ひれいする記憶領域きおくりょういきを使用しようしないため、補助空間計算量ほじょくうかんけいさんりょうは $$\mathrm{\Theta }\left(1\right)$$\Theta(1) である。

$$n=0$$n=0 の場合ばあいは比較ひかくを実行じっこうせず、直ただちに探索失敗たんさくしっぱいを返かえす。

6適用範囲てきようはんいと二分探索にぶんたんさくへの接続せつぞく

線形探索せんけいたんさくは、要素ようそを順次取得じゅんじしゅとくして等値比較とうちひかくできれば適用てきようでき、整列せいれつを必要ひつようとしない。一方いっぽう、整列済せいれつずみ配列はいれつでは、順序情報じゅんじょじょうほうにより複数ふくすうの候補こうほを一括いっかつして除外じょがいできる。次つぎの講義こうぎでは、この性質せいしつを利用りようする二分探索にぶんたんさくを説明せつめいする。

7まとめ

• 線形探索せんけいたんさくは、配列要素はいれつようそを先頭せんとうから順じゅんに目標値もくひょうちと比較ひかくする。
• ループ不変条件ふへんじょうけんの初期化しょきか、保存ほぞん、終了しゅうりょうにより、最初さいしょの一致位置いっちいちまたは探索失敗たんさくしっぱいを正ただしく返かえすことが証明しょうめいされる。
• 最良時間計算量さいりょうじかんけいさんりょうは $$\mathrm{\Theta }\left(1\right)$$\Theta(1)、最悪時間計算量さいあくじかんけいさんりょうは $$\mathrm{\Theta }\left(n\right)$$\Theta(n)、補助空間計算量ほじょくうかんけいさんりょうは $$\mathrm{\Theta }\left(1\right)$$\Theta(1) である。