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

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) である。

Linear Search

1Introduction

This lecture explains the procedure, correctness, and complexity of linear search, which compares array elements in order from the beginning. For an arbitrary array, when the algorithm uses only equality comparisons and assumes neither sorted order nor an auxiliary lookup structure, a comparison with one element cannot eliminate other elements collectively. Each element must therefore be examined individually.

2Problem statement and terminology

Let

be an array of length $$n$$n, and let $$x$$x be a target value. If some index $$i$$i satisfies $$A_i=x$$A_i=x, the algorithm returns the smallest such index. If no such index exists, it reports failure.

Linear search compares $$A_0,A_1,\dots ,A_{n-1}$$A_0,A_1,\ldots,A_{n-1} with the target in this order and terminates at the first match. The number of comparisons is the number of evaluations of the equality $$A_i=x$$A_i=x.

3Procedure

For $$i=0,1,\dots ,n-1$$i=0,1,\ldots,n-1 in order, perform the following steps.

1. Evaluate $$A_i=x$$A_i=x.
2. If the equality holds, return $$i$$i and terminate.
3. Otherwise, proceed to the next index.

If no index produces a match, report failure. This procedure does not depend on whether the array is sorted.

4Correctness by a loop invariant

A loop invariantLoop invariant is a proposition that holds at a designated point of every iteration. Immediately before the comparison at index $$i$$i, use the invariant

4.1Initialization

Immediately before the first comparison, $$i=0$$i=0. No element has been compared, so the invariant holds over the empty set of preceding indices.

4.2Maintenance

Assume that the invariant holds immediately before the comparison at index $$i$$i. If $$A_i=x$$A_i=x, no smaller index contains a match, so $$i$$i is the smallest index satisfying the specification. If $$A_i\ne x$$A_i\ne x, none of $$A_0,\dots ,A_i$$A_0,\ldots,A_i equals $$x$$x. The invariant therefore holds immediately before the comparison at index $$i+1$$i+1.

4.3Termination

If the algorithm terminates at a match, the maintenance argument shows that the returned index is the first matching position. If it reaches $$i=n$$i=n without a match, the invariant shows that none of $$A_0,\dots ,A_{n-1}$$A_0,\ldots,A_{n-1} equals $$x$$x. Reporting failure is therefore correct.

Initialization, maintenance, and termination together prove that linear search satisfies its specification.

5Complexity

Assume $$n>0$$n>0. In the best case, the target equals the first element $$A_0$$A_0. The algorithm performs one comparison, so its best-case running time is $$\mathrm{\Theta }\left(1\right)$$\Theta(1).

If the target occurs only at the final element or does not occur in the array, the algorithm performs $$n$$n comparisons. Its worst-case running time is therefore $$\mathrm{\Theta }\left(n\right)$$\Theta(n). Apart from its index and return value, it uses no storage proportional to the input length, so its auxiliary-space complexity is $$\mathrm{\Theta }\left(1\right)$$\Theta(1).

When $$n=0$$n=0, the algorithm performs no comparisons and reports failure immediately.

6Applicability and connection to binary search

Linear search requires only sequential access to elements and equality comparison; it does not require sorted order. In a sorted array, however, order information can eliminate multiple candidates at once. The next lecture explains binary search, which uses this property.

7Summary

• Linear search compares array elements with the target in order from the beginning.
• Initialization, maintenance, and termination of the loop invariant prove that the algorithm correctly returns the first matching position or reports failure.
• Its best-case running time is $$\mathrm{\Theta }\left(1\right)$$\Theta(1), its worst-case running time is $$\mathrm{\Theta }\left(n\right)$$\Theta(n), and its auxiliary-space complexity is $$\mathrm{\Theta }\left(1\right)$$\Theta(1).