>> [音楽再生]
DOUG LLOYD：リニア 検索は、アルゴリズムたちです
配列の要素を見つけるために使用することができます。
アルゴリズムのリコール ステップバイステップのセットです
タスクを完了するための手順の。
>> リニアサーチ アルゴリズムは次のように動作します。
左からアレイ全体で繰り返し処理 右、指定された要素を探しています。
>> もっとある擬似コードでは、 この文のバージョンを蒸留し、
最初の要素は何である場合 あなたが探している、あなたが停止することができます。
それ以外の場合は、次の要素に移動し、 あなたが見つかるまで何度も続けます
要素、またはあなたはしないでください。
だから我々は、直線を使用することができます 探索アルゴリズム、例えば、
目標値を見つけるために この配列の9。
さて、私たちは最初から開始。
それは我々がしているものなら 探して、私たちは停止することができます。
それは我々が11のために見ていない、ではありません。
だからそれ以外の場合は、次の要素に移動します。
>> だから我々は23を見てください。
我々が探しているものを23か？
まあ無いので、次に移動 要素、および次の要素、
我々はを通して続けます 何度もこのプロセス
私たちは着陸まで、オーバー このような状況に。
>> ナインは、我々が探しているものであり、 、配列のこのエレメント
それの値が9です。
そして、私たちは私たちがしているものを発見しました 探している、と私たちは停止することができます。
線形検索が持っています 正常に完了しました。
>> しかし、私たちが探している場合について 私たちの配列にない要素。
リニア検索はまだ動作しますか？
よく確認してください。
だから我々は、このプロセスを繰り返します 最初の要素から始まります。
それは我々がしているものなら 探して、私たちは停止することができます。
そうではありません。
そうでなければ、私たちは次の要素に移動します。
>> しかし、我々は、このプロセスを繰り返し続けることができます 順番に各要素を調べ、
私たちは数50を見つけることを期待。
しかし、我々は次の場合に知ることができません 私たちは数50を見つけました
私たちはしなかった場合は、我々は階段状するまで 配列のすべての単一の要素を超えます。
>> 一度だけ、私たちはやりました それと短い思い付きます、
我々は結論付けることができます 50は配列ではありません。
そしてそう線形検索 アルゴリズム、それが失敗しただけでなく、それ自体が。
しかし、ない意味でそれそれ 何をしている中で失敗しました
私たちは何をすることを求めました。
>> これは、中に失敗しました それは50を見つけられませんでしたように多くの、
しかし50は、配列ではありませんでした。
しかし、我々は徹底的に検索しました 一つ一つの素子を介して
そのため、我々は見つけることができませんでしたしながら、 何でも、リニアサーチまだ
成功しても 要素が配列ではありません。
>> だから、最悪の場合は何 線形探索とシナリオ？
さて、私たちは目を通す必要はあり 一つ一つの要素、
いずれかのためにターゲット要素 配列の最後の要素であり、
あるいは我々が探している要素がありません 実際にすべての配列に存在しています。
最良のシナリオは何ですか？
まあ我々は見つけるかもしれません すぐに要素。
そして、どのように多くの要素 私たちはその後を見ていますか
最良の場合でに、 我々はそれを探しているなら
そして、我々は非常に最初にそれを見つけますか？
我々はすぐに停止することができます。
>> これは約何と言っています リニアサーチの複雑？
まあ、最悪の場合には、我々が持っています 一つ一つの要素を見て。
そしてそれは、Oで実行されます 最悪の場合、nは、。
>> 最良のケースでは、我々はつもりです すぐに要素を見つけます。
だから1のオメガで実行されます。
>> 私はダグロイドです。
これはCS50です。