線形探索

コンピュータサイエンスにおいて、線形探索または順次探索はリスト内の要素を見つける方法である。一致するものが見つかるか、リスト全体が検索されるまで、リストの各要素を順番にチェックする。^[1]

線形探索は最悪の場合でも線形時間で実行され、最大でn 回の比較が行われます。ここでn はリストの長さです。各要素が等しく検索される可能性がある場合、線形探索の平均ケースは ⁠ です。1+1 番目/2⁠比較では平均ケースは影響を受けますが、各要素の検索確率が異なると、平均ケースは影響を受ける可能性があります。バイナリ検索アルゴリズムやハッシュテーブルなどの他の検索アルゴリズムやスキームを使用すると、短いリストを除いて大幅に高速な検索が可能になるため、線形検索はほとんど実用的ではありません。 ^[2]

線形探索は、リストの各要素を順番にチェックし、目的の値に一致する要素が見つかるまで続けます。アルゴリズムがリストの末尾に到達した場合、探索は失敗として終了します。^[1]

値またはレコードL ₀ .... L _{n −1を持つ}n個の要素のリストLとターゲット値Tが与えられた場合、次のサブルーチンは線形探索を使用してL内のターゲットTのインデックスを検索します。^[3]

1. i を0 に設定します。
2. L _i = Tの場合、検索は正常に終了し、iを返します。
3. iを 1増やします。
4. i < nの場合は、手順 2 に進みます。それ以外の場合、検索は失敗して終了します。

上記の基本アルゴリズムは、反復ごとに2つの比較を行います。1つはL _{i が}Tに等しいかどうかをチェックし、もう1つはi がリストの有効なインデックスを指しているかどうかをチェックします。ターゲットに等しい追加のレコードL _n (センチネル値) をリストに追加することで、2番目の比較を検索の最後まで排除することができ、アルゴリズムが高速になります。ターゲットがリストに含まれていない場合、検索はセンチネルに到達します。^[5]

1. i を0 に設定します。
2. L _i = Tの場合は、手順 4 に進みます。
3. i を1増やして手順 2 に進みます。
4. i < nの場合、検索は正常に終了し、iを返します。それ以外の場合、検索は失敗して終了します。

リストがL ₀ ≤ L ₁ ... ≤ L _{n −1となるように順序付けられている場合、} L _{i が}ターゲットを超えた時点で検索を終了することで、ターゲットの不在をより迅速に確認することができます。このバリエーションでは、ターゲットよりも大きいセンチネルが必要です。^[6]

1. i を0 に設定します。
2. L _i ≥ Tの場合はステップ4に進みます。
3. i を1増やして手順 2 に進みます。
4. L _i = Tの場合、検索は正常に終了し、iを返します。それ以外の場合、検索は失敗して終了します。

n個の項目を持つリストの場合、最良のケースは、値がリストの最初の要素と等しい場合です。この場合、必要な比較は 1 回だけです。最悪のケースは、値がリストにない場合 (またはリストの最後に 1 回だけ出現する場合) です。この場合、n 回の比較が必要になります。

探している値がリスト内でk回出現し、リストの順序がすべて同じ確率である場合、比較の期待回数は

${\displaystyle {\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}}$

たとえば、検索対象の値がリストに1回出現し、リストのすべての順序が等しく起こり得る場合、比較の期待回数は です。ただし、 1回出現することが分かっている場合は、最大でn - 1回の比較が必要であり、比較の期待回数は ${\displaystyle {\frac {n+1}{2}}}$

${\displaystyle \displaystyle {\frac {(n+2)(n-1)}{2n}}}$

(たとえば、n = 2 の場合、これは 1 となり、単一の if-then-else 構造に対応します)。

いずれにしても、漸近的には最悪の場合のコストと線形探索の期待コストはどちらもO ( n ) です。

目的の値がリストの末尾よりも先頭近くにある可能性が高い場合、線形検索のパフォーマンスが向上します。したがって、一部の値が他の値よりも検索される可能性がはるかに高い場合は、それらの値をリストの先頭に配置することが望ましいです。

特に、リスト項目が確率の降順で並べられ、これらの確率が幾何分布している場合、線形探索のコストはO(1)のみとなる。^[7]

線形検索は通常、実装が非常に簡単で、リストに要素が少ない場合や、順序付けられていないリストで単一の検索を実行する場合に実用的です。

同じリスト内で多数の値を検索する必要がある場合、より高速な方法を使用するためにリストを前処理すると効果的です。たとえば、リストをソートしてバイナリ検索を使用したり、そこから効率的な検索データ構造を構築したりすることができます。リストの内容が頻繁に変更される場合、繰り返しの再編成は手間がかかるだけでなく、価値がないこともあります。

その結果、理論上は他の検索アルゴリズム（例えば二分探索）の方が線形探索よりも高速である可能性があるものの、実際には中規模の配列（約100項目以下）であっても、他の方法を使用することは不可能である可能性があります。より大きな配列では、データが十分に大きい場合にのみ、他のより高速な検索方法を使用するのが理にかなっています。これは、データを準備（ソート）するための初期時間が、多くの線形探索に匹敵するためです。^[4]

• 三元検索
• ハッシュテーブル
• 線形探索問題

• Knuth, Donald (1998)。『ソートと検索。コンピュータプログラミングの芸術。第 3 巻 (第 2 版)。マサチューセッツ州レディング: Addison-Wesley Professional。  0-201-89685-0出版年月日