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