1
00:00:00,000 --> 00:00:02,892
>> [音楽再生]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD：リニア
検索は、アルゴリズムたちです

4
00:00:07,180 --> 00:00:09,840
配列の要素を見つけるために使用することができます。

5
00:00:09,840 --> 00:00:11,990
アルゴリズムのリコール
ステップバイステップのセットです

6
00:00:11,990 --> 00:00:15,030
タスクを完了するための手順の。

7
00:00:15,030 --> 00:00:17,480
>> リニアサーチ
アルゴリズムは次のように動作します。

8
00:00:17,480 --> 00:00:22,200
左からアレイ全体で繰り返し処理
右、指定された要素を探しています。

9
00:00:22,200 --> 00:00:26,380
>> もっとある擬似コードでは、
この文のバージョンを蒸留し、

10
00:00:26,380 --> 00:00:29,840
最初の要素は何である場合
あなたが探している、あなたが停止することができます。

11
00:00:29,840 --> 00:00:33,930
それ以外の場合は、次の要素に移動し、
あなたが見つかるまで何度も続けます

12
00:00:33,930 --> 00:00:36,389
要素、またはあなたはしないでください。

13
00:00:36,389 --> 00:00:38,680
だから我々は、直線を使用することができます
探索アルゴリズム、例えば、

14
00:00:38,680 --> 00:00:42,330
目標値を見つけるために
この配列の9。

15
00:00:42,330 --> 00:00:43,870
さて、私たちは最初から開始。

16
00:00:43,870 --> 00:00:45,970
それは我々がしているものなら
探して、私たちは停止することができます。

17
00:00:45,970 --> 00:00:47,890
それは我々が11のために見ていない、ではありません。

18
00:00:47,890 --> 00:00:50,220
だからそれ以外の場合は、次の要素に移動します。

19
00:00:50,220 --> 00:00:51,510
>> だから我々は23を見てください。

20
00:00:51,510 --> 00:00:52,730
我々が探しているものを23か？

21
00:00:52,730 --> 00:00:55,614
まあ無いので、次に移動
要素、および次の要素、

22
00:00:55,614 --> 00:00:57,780
我々はを通して続けます
何度もこのプロセス

23
00:00:57,780 --> 00:01:01,030
私たちは着陸まで、オーバー
このような状況に。

24
00:01:01,030 --> 00:01:03,910
>> ナインは、我々が探しているものであり、
、配列のこのエレメント

25
00:01:03,910 --> 00:01:05,787
それの値が9です。

26
00:01:05,787 --> 00:01:08,120
そして、私たちは私たちがしているものを発見しました
探している、と私たちは停止することができます。

27
00:01:08,120 --> 00:01:11,910
線形検索が持っています
正常に完了しました。

28
00:01:11,910 --> 00:01:15,370
>> しかし、私たちが探している場合について
私たちの配列にない要素。

29
00:01:15,370 --> 00:01:17,040
リニア検索はまだ動作しますか？

30
00:01:17,040 --> 00:01:17,540
よく確認してください。

31
00:01:17,540 --> 00:01:19,947
だから我々は、このプロセスを繰り返します
最初の要素から始まります。

32
00:01:19,947 --> 00:01:21,780
それは我々がしているものなら
探して、私たちは停止することができます。

33
00:01:21,780 --> 00:01:22,800
そうではありません。

34
00:01:22,800 --> 00:01:25,020
そうでなければ、私たちは次の要素に移動します。

35
00:01:25,020 --> 00:01:29,050
>> しかし、我々は、このプロセスを繰り返し続けることができます
順番に各要素を調べ、

36
00:01:29,050 --> 00:01:31,720
私たちは数50を見つけることを期待。

37
00:01:31,720 --> 00:01:33,750
しかし、我々は次の場合に知ることができません
私たちは数50を見つけました

38
00:01:33,750 --> 00:01:38,290
私たちはしなかった場合は、我々は階段状するまで
配列のすべての単一の要素を超えます。

39
00:01:38,290 --> 00:01:40,440
>> 一度だけ、私たちはやりました
それと短い思い付きます、

40
00:01:40,440 --> 00:01:43,040
我々は結論付けることができます
50は配列ではありません。

41
00:01:43,040 --> 00:01:46,410
そしてそう線形検索
アルゴリズム、それが失敗しただけでなく、それ自体が。

42
00:01:46,410 --> 00:01:49,181
しかし、ない意味でそれそれ
何をしている中で失敗しました

43
00:01:49,181 --> 00:01:49,930
私たちは何をすることを求めました。

44
00:01:49,930 --> 00:01:52,390
>> これは、中に失敗しました
それは50を見つけられませんでしたように多くの、

45
00:01:52,390 --> 00:01:54,070
しかし50は、配列ではありませんでした。

46
00:01:54,070 --> 00:01:57,310
しかし、我々は徹底的に検索しました
一つ一つの素子を介して

47
00:01:57,310 --> 00:02:00,550
そのため、我々は見つけることができませんでしたしながら、
何でも、リニアサーチまだ

48
00:02:00,550 --> 00:02:05,230
成功しても
要素が配列ではありません。

49
00:02:05,230 --> 00:02:07,507
>> だから、最悪の場合は何
線形探索とシナリオ？

50
00:02:07,507 --> 00:02:09,590
さて、私たちは目を通す必要はあり
一つ一つの要素、

51
00:02:09,590 --> 00:02:14,590
いずれかのためにターゲット要素
配列の最後の要素であり、

52
00:02:14,590 --> 00:02:18,510
あるいは我々が探している要素がありません
実際にすべての配列に存在しています。

53
00:02:18,510 --> 00:02:19,760
最良のシナリオは何ですか？

54
00:02:19,760 --> 00:02:22,430
まあ我々は見つけるかもしれません
すぐに要素。

55
00:02:22,430 --> 00:02:24,360
そして、どのように多くの要素
私たちはその後を見ていますか

56
00:02:24,360 --> 00:02:26,859
最良の場合でに、
我々はそれを探しているなら

57
00:02:26,859 --> 00:02:28,400
そして、我々は非常に最初にそれを見つけますか？

58
00:02:28,400 --> 00:02:29,850
我々はすぐに停止することができます。

59
00:02:29,850 --> 00:02:32,984
>> これは約何と言っています
リニアサーチの複雑？

60
00:02:32,984 --> 00:02:35,650
まあ、最悪の場合には、我々が持っています
一つ一つの要素を見て。

61
00:02:35,650 --> 00:02:38,930
そしてそれは、Oで実行されます
最悪の場合、nは、。

62
00:02:38,930 --> 00:02:41,540
>> 最良のケースでは、我々はつもりです
すぐに要素を見つけます。

63
00:02:41,540 --> 00:02:44,750
だから1のオメガで実行されます。

64
00:02:44,750 --> 00:02:45,780
>> 私はダグロイドです。

65
00:02:45,780 --> 00:02:48,020
これはCS50です。

66
00:02:48,020 --> 00:02:49,876