[音楽再生] DOUG LLOYD：リニア 検索は、アルゴリズムたちです 配列の要素を見つけるために使用することができます。 アルゴリズムのリコール ステップバイステップのセットです タスクを完了するための手順の。 

リニアサーチ アルゴリズムは次のように動作します。 左からアレイ全体で繰り返し処理 右、指定された要素を探しています。 

もっとある擬似コードでは、 この文のバージョンを蒸留し、 最初の要素は何である場合 あなたが探している、あなたが停止することができます。 それ以外の場合は、次の要素に移動し、 あなたが見つかるまで何度も続けます 要素、またはあなたはしないでください。 だから我々は、直線を使用することができます 探索アルゴリズム、例えば、 目標値を見つけるために この配列の9。 さて、私たちは最初から開始。 それは我々がしているものなら 探して、私たちは停止することができます。 それは我々が11のために見ていない、ではありません。 だからそれ以外の場合は、次の要素に移動します。 

だから我々は23を見てください。 我々が探しているものを23か？ まあ無いので、次に移動 要素、および次の要素、 我々はを通して続けます 何度もこのプロセス 私たちは着陸まで、オーバー このような状況に。 

ナインは、我々が探しているものであり、 、配列のこのエレメント それの値が9です。 そして、私たちは私たちがしているものを発見しました 探している、と私たちは停止することができます。 線形検索が持っています 正常に完了しました。 

しかし、私たちが探している場合について 私たちの配列にない要素。 リニア検索はまだ動作しますか？ よく確認してください。 だから我々は、このプロセスを繰り返します 最初の要素から始まります。 それは我々がしているものなら 探して、私たちは停止することができます。 そうではありません。 そうでなければ、私たちは次の要素に移動します。 

しかし、我々は、このプロセスを繰り返し続けることができます 順番に各要素を調べ、 私たちは数50を見つけることを期待。 しかし、我々は次の場合に知ることができません 私たちは数50を見つけました 私たちはしなかった場合は、我々は階段状するまで 配列のすべての単一の要素を超えます。 

一度だけ、私たちはやりました それと短い思い付きます、 我々は結論付けることができます 50は配列ではありません。 そしてそう線形検索 アルゴリズム、それが失敗しただけでなく、それ自体が。 しかし、ない意味でそれそれ 何をしている中で失敗しました 私たちは何をすることを求めました。 

これは、中に失敗しました それは50を見つけられませんでしたように多くの、 しかし50は、配列ではありませんでした。 しかし、我々は徹底的に検索しました 一つ一つの素子を介して そのため、我々は見つけることができませんでしたしながら、 何でも、リニアサーチまだ 成功しても 要素が配列ではありません。 

だから、最悪の場合は何 線形探索とシナリオ？ さて、私たちは目を通す必要はあり 一つ一つの要素、 いずれかのためにターゲット要素 配列の最後の要素であり、 あるいは我々が探している要素がありません 実際にすべての配列に存在しています。 最良のシナリオは何ですか？ まあ我々は見つけるかもしれません すぐに要素。 そして、どのように多くの要素 私たちはその後を見ていますか 最良の場合でに、 我々はそれを探しているなら そして、我々は非常に最初にそれを見つけますか？ 我々はすぐに停止することができます。 

これは約何と言っています リニアサーチの複雑？ まあ、最悪の場合には、我々が持っています 一つ一つの要素を見て。 そしてそれは、Oで実行されます 最悪の場合、nは、。 

最良のケースでは、我々はつもりです すぐに要素を見つけます。 だから1のオメガで実行されます。 

私はダグロイドです。 これはCS50です。