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
找到目標值
九裡這陣。

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
而且使其在鄰
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